子集、排列、组合

发表于 | 分类于 ， ， |

回溯算法解决子集、排列、组合问题

78.子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序返回解集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int start){
        //将结果加入到res中
        res.push_back(temp);
        for(int i=start;i<nums.size();i++){
            //做选择
            temp.push_back(nums[i]);
            //回溯
            dfs(nums, i+1);
            //撤消选择
            temp.pop_back();
        }
    }
};

90.子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按任意顺序排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        //将元素排序
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int start){
        res.push_back(temp);
        for(int i=start;i<nums.size();i++){
            //剪枝,值相同的相邻树枝，只遍历一次
            if(i>start && nums[i]==nums[i-1]) continue;
            //做选择
            temp.push_back(nums[i]);
            //回溯
            dfs(nums, i+1);
            //撤销选择
            temp.pop_back();
        }
    }
};

77.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }
    void dfs(int n, int k, int start){
        //结束条件
        if(k==temp.size()){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<=n;i++){
            //做选择
            temp.push_back(i);
            //回溯
            dfs(n, k, i+1);
            //撤消选择
            temp.pop_back();
        }
    }
};

39.组合总和

给你一个 无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。candidates 中的同一个 数字可以无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    int sum=0;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);;
        return res;
    }
    void dfs(vector<int>& candidates, int target, int start){
        //结束条件
        if(sum>target){
            return;
        }
        if(sum==target){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<candidates.size();i++){
            //做选择
            temp.push_back(candidates[i]);
            sum += candidates[i];
            //回溯
            dfs(candidates, target, i);
            //撤消选择
            temp.pop_back();
            sum -= candidates[i];
        }
    }
};

40.组合总和 II

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

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

注意：解集不能包含重复的组合。 

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    int sum=0;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0);
        return res;
    }
    void dfs(vector<int>& candidates, int target, int start){
        //结束条件
        if(sum>target){
            return;
        }
        if(sum==target){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<candidates.size();i++){
            //剪枝，值相同的树枝，只遍历第一条
            if(i>start && candidates[i]==candidates[i-1]) continue;
            //做选择
            temp.push_back(candidates[i]);
            sum += candidates[i];
            //回溯
            dfs(candidates, target, i+1);
            //撤消选择
            temp.pop_back();
            sum -= candidates[i];
        }

    }
};

216.组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    int sum=0;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return res;
    }
    void dfs(int k, int n, int start){
        //结束条件
        if(sum>n){
            return;
        }
        if(temp.size()==k && sum==n){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<=9;i++){
            //做选择
            temp.push_back(i);
            sum += i;
            //回溯
            dfs(k, n, i+1);
            //撤消选择
            temp.pop_back();
            sum -= i;
        }
    }
};

46.全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<bool> isVisited;
    vector<vector<int>> permute(vector<int>& nums) {
        int n=nums.size();
        isVisited.resize(n, false);
        dfs(nums);
        return res;
    }
    void dfs(vector<int>& nums){
        //触发结束条件
        if(temp.size()==nums.size()){
            res.push_back(temp);
            return;
        }
        for(int i=0;i<nums.size();i++){
            //剪枝函数
            if(isVisited[i]) continue;
            //做选择
            isVisited[i]=true;
            temp.push_back(nums[i]);
            //回溯
            dfs(nums);
            //撤消选择
            temp.pop_back();
            isVisited[i]=false;
        }
    }
};

47.全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;
    vector<bool> isVisited;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        //先排序，让相同的元素靠在一起
        sort(nums.begin(), nums.end());
        int n=nums.size();
        isVisited.resize(n, false);
        dfs(nums);
        return res;
    }
    void dfs(vector<int>& nums){
        //触发结束条件
        if(temp.size()==nums.size()){
            res.push_back(temp);
            return;
        }
        for(int i=0;i<nums.size();i++){
            //剪枝
            if(isVisited[i]) continue;
            // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
            // 如果前面的相邻相等元素没有用过，则跳过
            if(i>0 && nums[i]==nums[i-1] && !isVisited[i-1]) continue; 
            //做选择
            isVisited[i]=true;
            temp.push_back(nums[i]);
            //回溯
            dfs(nums);
            //撤销选择
            temp.pop_back();
            isVisited[i]=false;
        }
    }
};

31.下一个排列

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
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //思路：两趟遍历
        //从后往前找到第一个逆序的数字，
        //然后找到该逆序数字后面比它大的最小数字
        //交换两个数的位置
        //对一开始逆序数位置后面的进行反转

        int i=nums.size()-2;
        //从后往前找到第一个逆序的数字
        while(i>=0 && nums[i]>=nums[i+1]){
            i--;
        }
        //找到该逆序数字后面比它大的最小数字
        if(i>=0){
            int j=nums.size()-1;
            while(j>=0 && nums[i]>=nums[j]){
                j--;
            }
            //交换
            swap(nums[i], nums[j]);
        }
        //对一开始逆序数位置后面的进行反转
        reverse(nums.begin()+i+1, nums.end());
    }
};
//时间复杂度：O(n)
//空间复杂度：O(1)
-------------本文结束 感谢阅读-------------
0%