Description
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
Solutions
1. Backtracking
这得判断前后两个数是否相同，相同就不要重复采用了，然后下一个数的起始点应该是 i+1 了！
# Time: O(n^target)
# Space: O(n)
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort()
self.dfs(candidates, 0, [], target, res)
return res
def dfs(self, candidates, start, path, target, res):
if target == 0:
res.append(path)
n = len(candidates)
for i in range(start, n):
if i > start and candidates[i] == candidates[i-1]:
continue
if target >= candidates[i]:
self.dfs(candidates, i + 1, path + [candidates[i]], target - candidates[i], res)
# 172/172 cases passed (68 ms)
# Your runtime beats 67.83 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)
2. 迭代解法
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans = [[] for i in range(target + 1)]
ans[0] = [[]]
candidates = sorted(candidates)
for i in candidates:
for j in range(target, -1, -1):
if i <= j:
for p in ans[j - i]:
if p + [i] not in ans[j]:
ans[j].append(p + [i])
return ans[target]