Combination Sum Problem

Question

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

 

Constraints:

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• Each element of candidate is unique.
• 1 <= target <= 500

Answer 1

As one can see, the above backtracking algorithm is unfolded as a DFS (Depth-First Search) tree traversal, which is often implemented with recursion.

Here we define a recursive function of backtrack(remain, comb, start) (in Python), which populates the combinations, starting from the current combination (comb), the remaining sum to fulfill (remain) and the current cursor (start) to the list of candidates. 

• For the first base case of the recursive function, if the remain==0, i.e. we fulfill the desired target sum, therefore we can add the current combination to the final list.
• As another base case, if remain < 0, i.e. we exceed the target value, we will cease the exploration here.
• Other than the above two base cases, we would then continue to explore the sublist of candidates as [start ... n]. For each of the candidate, we invoke the recursive function itself with updated parameters.
  • Specifically, we add the current candidate into the combination.
  • With the added candidate, we now have less sum to fulfill, i.e. remain - candidate.
  • For the next exploration, still we start from the current cursor start.
  • At the end of each exploration, we backtrack by popping out the candidate out of the combination.

class Solution:     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:         results = []         def backtrack(remain, comb, start):             if remain == 0:                 # make a deep copy of the current combination                 results.append(list(comb))                 return             elif remain < 0:                 # exceed the scope, stop exploration.                 return             for i in range(start, len(candidates)):                 # add the number into the combination                 comb.append(candidates[i])                 # give the current number another chance, rather than moving on                 backtrack(remain - candidates[i], comb, i)                 # backtrack, remove the number from the combination                 comb.pop()                  backtrack(target, [], 0)                  return results

eg : ans = Solution()

candidates = [2,3,5] 

target = 8

ans.combinationSum(candidates, target)

Output-

[

  [2,2,2,2],

  [2,3,3],

  [3,5]

]