【Day 81 】2024-02-04 - 40 组合总数 II

[azl397985856]

40 组合总数 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/combination-sum-ii/

前置知识

• 剪枝
• 数组
• 回溯

题目描述

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

[snmyj]

class Solution {
public:
    void solve(int i, vector<int>& candidates, int sum,
        vector<int>& ch, int target, vector<vector<int>>& ans) {
        if (sum == target) {
            ans.push_back(ch);
            return;
        }
        if (i == candidates.size() || sum > target)
            return;

        for (int j = i + 1; j < candidates.size(); j++)
            if (candidates[j] != candidates[i]) {
               
                solve(j, candidates, sum, ch, target, ans);
                break;
            }


        ch.push_back(candidates[i]);
        solve(i + 1, candidates, sum + candidates[i], ch, target, ans);
        ch.pop_back();
    }


    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        sort(candidates.begin(), candidates.end());
        vector<int> ch;
        solve(0, candidates, 0, ch, target, ans);
        return ans;
    }
};

[Junru281]

悄悄回归打卡!

几周没写, 又没感觉了. 看到题, 两眼一抹黑

参考题解...😭

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

    Arrays.sort(candidates);
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new LinkedList<>();
    helper(res, list, target, candidates, 0);
    return res;
}

public void helper(List<List<Integer>> res, List<Integer> list, int target, int[] candidates, int start) {
    //如果target已经被消耗完, 即为一个valid combination
    // test case
    if (target == 0) {
        res.add(new LinkedList<>(list));
        return;
    }
    // 从start位置开始, 
    for (int i = start; i < candidates.length; i++) {
        // target 比candidate要大, 才有可能是valid solution
        if (target - candidates[i] >= 0) {
            // 这里就是去重复的过程.
            // 因为一直是recursion tree所以其实包含该元素的tree已经搜过了
            // 不会错过1,1,1的情况是因为test case(base case)
            if (i > start && candidates[i] == candidates[i - 1])
                continue;

            list.add(candidates[i]);
            helper(res, list, target - candidates[i], candidates, i + 1);
            // 删掉最后一个的原因是: recursion call每次删除一个, 恢复原状
            list.remove(list.size() - 1);
        }
    }
}
}

时间复杂度里面有2^n 也是因为有recursion tree T(n) = T(n-k) + O(n-k). 不太确定

[larscheng]

思路

与39题的区别在于 candidates数组中的元素不可重复使用
所以在进行递归时，下一个待选择元素需要+1

观察示例1可以发现，因为candidates数组存在重复元素，所以结果集中会出现相同组合，所以还需要进行去重剪枝处理
画出树形图，可以观察到同一层中的元素不可以重复，同一个元素仅一次有效

代码

class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int length = candidates.length;
        List<List<Integer>> res = new ArrayList<>();

        Arrays.sort(candidates);
        Deque<Integer> queue = new ArrayDeque<>();
        dfs(candidates,0,target,length,queue,res);
        return res;
    }

    private void dfs(int[] candidates, int begin, int target, int length, Deque<Integer> queue, List<List<Integer>> res) {
        if (target==0){
            res.add(new ArrayList<>(queue));
            System.out.println();
            return;
        }

        for (int i = begin; i < length; i++) {
            if (target - candidates[i] < 0) {
                break;
            }
            //同一层相同元素进行剪枝
            if (i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }
            queue.addLast(candidates[i]);
            //递归元素+1
            dfs(candidates, i + 1, target - candidates[i], length, queue, res);

            queue.removeLast();
        }
    }
}

[adfvcdxv]

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

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);
    }
}

}