组合总和 II

40. 组合总和 II

给定一个候选人编号的集合 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 <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

相似题目

组合总和

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { } };

rust 解法, 执行用时: 1 ms, 内存消耗: 2.3 MB, 提交时间: 2025-01-26 01:10:16

impl Solution {
    pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        candidates.sort_unstable();
        fn dfs(i: usize, left: i32, candidates: &[i32], path: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
            // 所选元素之和恰好等于 target
            if left == 0 {
                ans.push(path.clone());
                return;
            }

            // 在 [i, candidates.len()-1] 中选一个 candidates[j]
            // 注意选 candidates[j] 意味着 [i,j-1] 中的数都没有选
            for j in i..candidates.len() {
                // 后面的数不需要选了，元素之和必然无法恰好等于 target
                if left < candidates[j] {
                    break;
                }
                // 考虑选 candidates[j]
                // 如果 j>i，说明 candidates[j-1] 没有选 
                // 同方法一，所有等于 candidates[j-1] 的数都不选
                if j > i && candidates[j] == candidates[j - 1] {
                    continue;
                }
                path.push(candidates[j]);
                dfs(j + 1, left - candidates[j], candidates, path, ans);
                path.pop(); // 恢复现场
            }
        }
        let mut ans = vec![];
        let mut path = vec![];
        dfs(0, target, &candidates, &mut path, &mut ans);
        ans
    }
}

javascript 解法, 执行用时: 4 ms, 内存消耗: 52.6 MB, 提交时间: 2025-01-26 01:09:57

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    candidates.sort((a, b) => a - b);
    const ans = [];
    const path = [];
    var dfs = function(i, left) {
        // 所选元素之和恰好等于 target
        if (left === 0) {
            ans.push([...path]);
            return;
        }

        // 在 [i, candidates.length-1] 中选一个 candidates[j]
        // 注意选 candidates[j] 意味着 [i,j-1] 中的数都没有选
        for (let j = i; j < candidates.length && candidates[j] <= left; j++) {
            // 如果 j>i，说明 candidates[j-1] 没有选 
            // 同方法一，所有等于 candidates[j-1] 的数都不选
            if (j > i && candidates[j] === candidates[j - 1]) {
                continue;
            }
            path.push(candidates[j]);
            dfs(j + 1, left - candidates[j]);
            path.pop(); // 恢复现场
        }
    };
    dfs(0, target);
    return ans;
};

golang 解法, 执行用时: 0 ms, 内存消耗: 4.3 MB, 提交时间: 2025-01-26 01:09:36

func combinationSum2(candidates []int, target int) (ans [][]int) {
    slices.Sort(candidates)
    path := []int{}
    var dfs func(int, int)
    dfs = func(i, left int) {
        // 所选元素之和恰好等于 target
        if left == 0 {
            ans = append(ans, slices.Clone(path))
            return
        }

        // 在 [i, len(candidates)-1] 中选一个 candidates[j]
        // 注意选 candidates[j] 意味着 [i,j-1] 中的数都没有选
        for j := i; j < len(candidates) && candidates[j] <= left; j++ {
            // 如果 j>i，说明 candidates[j-1] 没有选 
            // 同方法一，所有等于 candidates[j-1] 的数都不选
            if j > i && candidates[j] == candidates[j-1] {
                continue
            }
            path = append(path, candidates[j])
            dfs(j+1, left-candidates[j])
            path = path[:len(path)-1] // 恢复现场
        }
    }
    dfs(0, target)
    return ans
}

golang 解法, 执行用时: 2 ms, 内存消耗: 2.6 MB, 提交时间: 2024-04-23 14:43:17

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 解法, 执行用时: 38 ms, 内存消耗: 16.6 MB, 提交时间: 2024-04-23 14:42:50

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

java 解法, 执行用时: 3 ms, 内存消耗: 42.5 MB, 提交时间: 2024-04-23 14:42:34

class Solution {
    List<int[]> freq = new ArrayList<int[]>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }
}

cpp 解法, 执行用时: 7 ms, 内存消耗: 14.3 MB, 提交时间: 2024-04-23 14:42:16

// dfs
class Solution {
private:
    vector<pair<int, int>> freq;
    vector<vector<int>> ans;
    vector<int> sequence;

public:
    void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.push_back(sequence);
            return;
        }
        if (pos == freq.size() || rest < freq[pos].first) {
            return;
        }

        dfs(pos + 1, rest);

        int most = min(rest / freq[pos].first, freq[pos].second);
        for (int i = 1; i <= most; ++i) {
            sequence.push_back(freq[pos].first);
            dfs(pos + 1, rest - i * freq[pos].first);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for (int num: candidates) {
            if (freq.empty() || num != freq.back().first) {
                freq.emplace_back(num, 1);
            } else {
                ++freq.back().second;
            }
        }
        dfs(0, target);
        return ans;
    }
};

python3 解法, 执行用时: 168 ms, 内存消耗: 13.5 MB, 提交时间: 2020-09-09 22:02:42

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res = []
        def backtrack(candidates, tmp):
            if  sum(tmp) > target:
                return 
            if sum(tmp) == target:
                res.append(tmp)
                return 
            for i,k in enumerate(candidates):
                if i > 0 and k == candidates[i-1]:
                    continue
                backtrack(candidates[i+1:], tmp + [k])
            return res
        return backtrack(candidates, [])

上一题

下一题

详情