Combination Sum II Program (Leetcode)

Combination Sum II Program (Leetcode):

The Combination Sum II program on LeetCode is a problem that involves finding all unique combinations in a candidate set where the candidate numbers sum up to a given target. However, each number in the candidates may only be used once in each combination. This challenge extends the classic Combination Sum problem by adding the constraint of using each number only once. To solve this problem efficiently, candidates are sorted, and a backtracking algorithm is typically employed to explore all possible combinations while ensuring uniqueness. The program must handle duplicates in the candidate set and avoid generating duplicate combinations in the final result. This problem requires careful consideration of edge cases and proper handling of duplicates to produce the correct output efficiently.

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number  candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

 

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

#s sum of current set, k index, r  remaining sum
def subset(s, k, r): 
    x[k] = 1
    if s + nums[k] == target:
        p = []
        for i in range(k + 1):
            if x[i] == 1:
                p.append(nums[i])

            val.append(p)

    elif s + r >= target and s + nums[k] <= target:
    subset(s + nums[k], k + 1, r - nums[k])
    if s - nums[k] + r >= target and s + nums[k + 1] <= target:
        x[k] = 0
        subset(s, k + 1, r - nums[k])

x = [0 for i in range(len(nums))] #index
nums.sort()

val = []
subset(0, 0, sum(nums))        
ans = []
for i in val:
    if i not in ans:
        ans.append(i)

return ans