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.
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
Input: candidates = [2,3,6,7], target = 7, A solution set is: [ , [2,2,3] ]
Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ]
Use backtracking. A partial solution is 0 or more candidates with a sum smaller or equal to target. Each recursion adds a number larger or equal to the last iteration to eliminate duplication.
For more information on backtracking, see this note.
Python objects are passed by reference. Thus, to make a copy of a list when a solution is found, use
a_list[:] to copy a new reference before adding to the result set. Or create a new list for every recursion with
progress + [c].
class Solution: def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ solutions = list() progress = list() candidates.sort() size = len(candidates) def backtrack(last_index, remaining): if remaining < 0: return if remaining == 0: solutions.append(list(progress)) # copy progress return if remaining > 0: for idx in range(last_index, size): c = candidates[idx] if c <= remaining: progress.append(c) backtrack(idx, remaining - c) progress.pop() return backtrack(0, target) return solutions