class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
}
};
剑指 Offer II 082. 含有重复元素集合的组合
给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5], target =8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
注意：本题与主站 40 题相同： https://leetcode.cn/problems/combination-sum-ii/
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2022-11-23 10:57:42
func combinationSum2(candidates []int, target int) (ans [][]int) {
sort.Ints(candidates)
var freq [][2]int
for _, num := range candidates {
if freq == nil || num != freq[len(freq)-1][0] {
freq = append(freq, [2]int{num, 1})
} else {
freq[len(freq)-1][1]++
}
}
var sequence []int
var dfs func(pos, rest int)
dfs = func(pos, rest int) {
if rest == 0 {
ans = append(ans, append([]int(nil), sequence...))
return
}
if pos == len(freq) || rest < freq[pos][0] {
return
}
dfs(pos+1, rest)
most := min(rest/freq[pos][0], freq[pos][1])
for i := 1; i <= most; i++ {
sequence = append(sequence, freq[pos][0])
dfs(pos+1, rest-i*freq[pos][0])
}
sequence = sequence[:len(sequence)-most]
}
dfs(0, target)
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
python3 解法, 执行用时: 24 ms, 内存消耗: 15 MB, 提交时间: 2022-11-23 10:57:20
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(pos: int, rest: int):
nonlocal sequence
if rest == 0:
ans.append(sequence[:])
return
if pos == len(freq) or rest < freq[pos][0]:
return
dfs(pos + 1, rest)
most = min(rest // freq[pos][0], freq[pos][1])
for i in range(1, most + 1):
sequence.append(freq[pos][0])
dfs(pos + 1, rest - i * freq[pos][0])
sequence = sequence[:-most]
freq = sorted(collections.Counter(candidates).items())
ans = list()
sequence = list()
dfs(0, target)
return ans