Skip to main content

Combination Sum II

Question​

Given an array of distinct integers and a target sum, find all unique combinations of the integers in the array with the elements adding up to the target sum.

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

Output:
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

Solution​

all//Combination Sum II.py


def combinationSum2(candidates, target):
    res = []
    candidates.sort()
    dfs(candidates, target, 0, [], res)
    return res

def dfs(nums, target, index, path, res):
    if target < 0:
        return  # backtracking
    if target == 0:
        res.append(path)
        return
    for i in range(index, len(nums)):
        if i > index and nums[i] == nums[i-1]:
            continue
        dfs(nums, target-nums[i], i+1, path+[nums[i]], res)