Combination Sum - Backtracking / Dedup

Problems
24

Why do we need to sort candidates? The solutions works just as well on unsorted candidates??

1 Like
25

This does not make sense to me:

To do that, we just need to add an extra condition to prune the duplicate branches

1if remaining - num < 0:
2    break

How does this prevent duplicates from being chosen?

2 Likes
26

I find this solution is more intutitive than the dedup solution. As I dont understand dedup fully. I managed to solve it using Algomonster’s Backtracking template 2

def combination_sum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        def dfs(current_sum, nums, start):
            if current_sum == target:
                res.append(nums[:])
                return
        
            for idx in range(start, len(candidates)):
                candidate = candidates[idx]
                if candidate + current_sum <= target:
                    nums.append(candidate)
                    dfs(candidate + current_sum, nums, idx)
                    nums.pop()
                else:
                    break
        candidates.sort()
        dfs(0, [], 0)
        return res
27

I have the same question. I think it must be a typo.

28

I second this question. Some clarification should be added to this section to explain why we sort. It seems to me that sorting candidates only makes resulting combinations sorted internally, but the problem statement doesn’t specify that this is required.

29

I have the same question. Drawing out the state tree it looks like there would be duplicate sub-trees any time you get to the same remainder. But I’m not clear on where I would trigger a result cache. Mods, any tips?

30

I agree. I think sorting is needed if the candidates array isn’t guaranteed to contain unique values, but it is in this case.

31

The solution is wrong, try this
[10,1,2,7,6,1,5] and target = 8
Your solution will produce duplicates

This is my solution and it works without duplicates.

def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
    
    result = []
    candidates.sort()

    def dfs(index, acc, combination):
        if index == len(candidates):
            return
        if acc > target:
            return
        if acc == target:
            result.append(combination[:])

        for i in range(index, len(candidates)):
            if i > 0 and candidates[i] == candidates[i - 1]:
                continue
            combination.append(candidates[i])
            dfs(i, acc + candidates[i], combination)
            combination.pop()

    dfs(0, 0, [])

    return result
32

@Uzair @Johnathan_Simeroth

I think it’s possible, but I haven’t proven it yet.

One could build a cache of vector<vector> for every starting search index and target (or remainder), though this feels kind of brutal in terms of memory usage in large cases.

At least, I think the state in this case is defined as both the search start index and the target.

The recursion should push all the way to the “right” in the candidates, and subsequent stack frames on the way up should benefit from the smaller results.

Would definitely appreciate some TA/Mod input on this.

33

Non iterative approach

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> output = new ArrayList<>();
        backTrack(0, 0, target, new ArrayList<>(), candidates, output);
        return output;
    }

    public void backTrack(int sum, int index, int target, ArrayList<Integer> path, int[] candidates, List<List<Integer>> output) {
        if (sum > target) return;
        if (index >= candidates.length) return;

        if (sum == target) {
            output.add(new ArrayList<>(path));
            return;
        }

        int num = candidates[index];
        path.add(num);
        // choosing the same number again
        backTrack(sum + num, index, target, path, candidates, output);
        path.remove(path.size() - 1);
        // removing last added number and choosing new number
        backTrack(sum, index + 1, target, path, candidates, output);
    }
34

The Python code is giving a wrong output for the input [2, 2, 4] and 6. In particular, it’s giving:

2 2 2
2 2 2
2 2 2
2 2 2
2 4
2 4

that contains a lot of duplicated tuples.

35 
def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
    combs = []
    def dfs(start_index, cur_comb, tot_sum):
        if tot_sum == target:
            combs.append(cur_comb[:])
            return
        if tot_sum > target:
            return
        for i in range(start_index, len(candidates)):
            cand = candidates[i]
            cur_comb.append(cand)           
            dfs(i, cur_comb, tot_sum + cand)
            cur_comb.pop()
    candidates.sort()
    dfs(0, [], 0)
    return combs
36

If you read the problem’s constraints carefully, it says all candidate elements are distinct.

37

But there are no guarantees that all inputs are sorted. Perhaps the examples should have unsorted input to avoid confusion.