Given an array num and a number target. Find all unique combinations in num where the numbers sum to target.
Each number in num can only be used once in one combination. All numbers (including target) will be positive integers. Numbers in a combination a1, a2, … , ak must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak) Different combinations can be in any order. The solution set must not contain duplicate combinations.
Example 1:
Input: num = [7,1,2,5,1,6,10], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Example 2:
Input: num = [1,1,1], target = 2
Output: [[1,1]]
Explanation: The solution set must not contain duplicate combinations.
class Solution:
"""
@param candidates: A list of integers
@param target: An integer
@return: A list of lists of integers
"""
def combinationSum2(self, candidates, target):
ans = []
cur = []
csum = 0
self.traverse(sorted(candidates), target, ans, cur, csum)
return ans
def traverse(self, candidates, target, ans, cur, csum):
if csum == target:
ans.append(cur[:])
return
if csum > target:
return
for i, c in enumerate(candidates):
if i > 0:
if c == candidates[i-1]:
continue
cur.append(c)
csum += c
self.traverse(candidates[i+1:], target, ans, cur, csum)
csum -= c
cur.pop()
return
Given a set of candidtate numbers candidates and a target number target. Find all unique combinations in candidates where the 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. Numbers in a combination a1, a2, … , ak must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak) Different combinations can be in any order. The solution set must not contain duplicate combinations.
Example 1
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[7], [2, 2, 3]]
Example 2:
Input: candidates = [1], target = 3
Output: [[1, 1, 1]]
只有一行的差别。
self.traverse(candidates[i:], target, ans, cur, csum)
candidates[i+1:]
,意思是本元素不再参与下一层递归。意思是元素不能重复使用candidates[i:]
,意思是本元素可以重复使用。