Luobuyu's Blog

0%

40.组合总和II

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.3k 阅读时长 ≈ 1 分钟
类似组合数2，也就是存在重复数字，求子集。排序，剪枝。

40.组合总和 II

题目描述：

给出一个存在重复元素的长度为 $ n $ 整数数组candidates和一个目标整数target，找出能够使数字和为目标数target的所有不同组合，并返回。

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

并且解集中不能包含重复的组合。

数据范围：
$ 1\le n \le 100, 2\le candidates[i] \le 50 $

题解：

其实就是带重复数字的组合数问题。和重复数字问题的思路一样，先排序，然后使用标记数组。

if(step>0 && nums[step] == nums[step-1] && !vis[step - 1])满足条件的话不选当前的数，直接进入下一个位置。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    vector<vector<int>> ans;
    void dfs(int step, int sum, int target, vector<int> &cur, vector<int> &nums, vector<bool>& vis)
    {
        if (sum == target)
        {
            ans.emplace_back(cur);
            return;
        }
        if (sum > target)
            return;
        if (step == nums.size())
            return;
        if(step > 0 && nums[step] == nums[step - 1] && !vis[step - 1])
        {
            dfs(step + 1, sum, target, cur, nums, vis);
        }
        else
        {
            cur.emplace_back(nums[step]);
            vis[step] = true;
            dfs(step + 1, sum + nums[step], target, cur, nums, vis);
            vis[step] = false;
            cur.pop_back();
            dfs(step + 1, sum, target, cur, nums, vis);
        }

    }
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<int> cur;
        vector<bool> vis(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        dfs(0, 0, target, cur, candidates, vis);
        return ans;
    }
};