Combination Sum

Question

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

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

https://leetcode.com/problems/combination-sum/description/

Same idea but to find all the possible combination of number inside an array to reach to a target sum

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Time Complexity: $O(2^{target})$

• For each number we can choose or not choose, therefore $2$.
• If at a number we can only choose 2 options (take or not take) without being allowed to visit the same number, it would be $2^n$
  • However, we have to calculate up to a $target$. Worst come to worst we have at most $target$ number for that number. So it's $2^{target}$

Space complexity: $O(\text{length of longest combination})$

• The height of the recursion tree which is the length of the longest combination

General algorithm

Following the same pattern from Subset, we have

class App():
    result: List[List[int]]
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.result = []
        self._combinationSum(candidates, 0, target)
        return self.result
    
    def _combinationSum(self, candidates, index, target, selected = []) -> None:
        if target < 0: return

        if target == 0:
            self.result.append(selected.copy())
            return

        for i in range(index, len(candidates)):
            selected.append(candidates[i])
            self._combinationSum(candidates, i, target - candidates[i], selected)
            selected.pop()

Note: in here we use for i loop to always choose the number to the right. Therefore we can avoid going backwards, which prevents to generate same solution but with different order (for example [2,2,3], [2,3,2])

For backtracking we start from the same i as the question allows us to choose the same number multiple times.

Recursion loop order.

For example if we have the input [2,3,6,7] and have the print statement at the start:

    def _combinationSum(self, candidates, index, target, selected = []) -> None:
        print("Selected", selected)
        if target < 0: return

        if target == 0:
            self.result.append(selected.copy())
            return

	    ...

We have the following output

Selected []
Selected [2]
Selected [2, 2]
Selected [2, 2, 2]
Selected [2, 2, 2, 2]
Selected [2, 2, 2, 3]
Selected [2, 2, 2, 6]
Selected [2, 2, 2, 7]
Selected [2, 2, 3]
Selected [2, 2, 6]
Selected [2, 2, 7]
Selected [2, 3]
Selected [2, 3, 3]
Selected [2, 3, 6]
Selected [2, 3, 7]
Selected [2, 6]
Selected [2, 7]
Selected [3]
Selected [3, 3]
Selected [3, 3, 3]
Selected [3, 3, 6]
Selected [3, 3, 7]
Selected [3, 6]
Selected [3, 7]
Selected [6]
Selected [6, 6]
Selected [6, 7]
Selected [7]

No duplication, can't use the same number

Combination Sum II - LeetCode

class App():
    result: List[List[int]]
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
		self.result = []
        self._combinationSum(sorted(candidates), 0, target)
        return self.result
    
    def _combinationSum(self, candidates, index, target, selected = []) -> None:
        if target < 0: return

        if target == 0:
            self.result.append(selected.copy())
            return

        for i in range(index, len(candidates)):
            if i > index and candidates[i] == candidates[i - 1]:
                continue

            selected.append(candidates[i])
            self._combinationSum(candidates, i + 1, target - candidates[i], selected)
            selected.pop()

[!note]
For this question, we need to sort because the candidates given are not in any particular order. Therefore it's not possible to know if a number has been chosen or not

Also for this question, rule is each number can only be selected once, not like the above question, therefore, we need to do i + 1 in the _combinationSum for the index

In here we use the same method as Subset > Subset duplication as we only allowed unique result in the array (cannot have [2,2,1] and [1,2,2] in the same result)

We use i+1 because we cannot use the same number