【刷题篇】回溯算法(三)

文章目录

• 1、全排列
• 2、子集
• 3、找出所有子集的异或总和再求和
• 4、全排列 II
• 5、电话号码的字母组合
• 6、括号生成

1、全排列

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

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    //vector<bool> sign(7);并不能使用它，它并不能使用[],底层储存问题
    bool sign[7];
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);
        return ret;
    }

    void dfs(vector<int>& nums)
    {
        if(nums.size()==path.size())
        {
            ret.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(sign[i]==false)
            {
                path.push_back(nums[i]);
                sign[i]=true;
                dfs(nums);
                path.pop_back();
                sign[i]=false;
            }
        }
    }
};
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

2、子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums,0);
        return ret;
    }
    //解法一
    // void dfs1(vector<int> nums,int i)
    // {
    //     if(i==nums.size())
    //     {
    //         ret.push_back(path);
    //         return;
    //     }
    //     //选
    //     path.push_back(nums[i]);
    //     dfs(nums,i+1);
    //     path.pop_back();
    //     //不选
    //     dfs(nums,i+1);
    // }
    //解法二
    void dfs(vector<int> nums,int pos)
    {
        ret.push_back(path);
        for(int i=pos;i<nums.size();i++)
        {
            path.push_back(nums[i]);
            dfs(nums,i+1);
            path.pop_back();
        }
    }
};
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

3、找出所有子集的异或总和再求和

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
注意：在本题中，元素 相同 的不同子集应 多次 计数。
数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

class Solution {
public:
    // vector<int> ret;
    // vector<int> path;
    // int subsetXORSum(vector<int>& nums) {
    //     dfs(nums,0);
    //     int sum=0;
    //     for(int i=0;i<ret.size();i++)
    //     {
    //         sum+=ret[i];
    //     }
    //     return sum;
    // }
    // void dfs(vector<int> nums,int pos)
    // {
    //     int sum=0;
    //     for(int i=0;i<path.size();i++)
    //     {
    //         sum^=path[i];
    //     }
    //     ret.push_back(sum);
    //     for(int i=pos;i<nums.size();i++)
    //     {
    //         path.push_back(nums[i]);
    //         dfs(nums,i+1);
    //         path.pop_back();
    //     }
    // }
    int sum=0;
    int path=0;
    int subsetXORSum(vector<int> nums)
    {
        dfs(nums,0);
        return sum;
    }
    void dfs(vector<int> nums,int pos)
    {
        sum+=path;//每次开始的节点都是我们需要的
        for(int i=pos;i<nums.size();i++)
        {
            path^=nums[i];
            dfs(nums,i+1);
            path^=nums[i];//恢复现场
        }

    }
};
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
43
44
45
46
47

4、全排列 II

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

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[8];
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());//方便后面处理分支
        dfs(nums,0);
        return ret;
    }
    void dfs(vector<int> nums,int pos)
    {
        if(pos==nums.size())
            ret.push_back(path);
        for(int i=0;i<nums.size();i++)
        {
            //剪枝方法一，只关心合法分支
            // if(check[i]==false&&(i==0||nums[i]!=nums[i-1]||(check[i-1]==true&&nums[i]==nums[i-1])))
            // {
            //     check[i]=true;
            //     path.push_back(nums[i]);
            //     dfs(nums,pos+1);
            //     check[i]=false;
            //     path.pop_back();
            // }
            //剪枝方法二,只关心不合法分支
            if(check[i]==true||(i!=0&&nums[i]==nums[i-1]&&check[i-1]==false))
                continue;
            check[i]=true;
            path.push_back(nums[i]);
            dfs(nums,pos+1);
            check[i]=false;
            path.pop_back();
        }
    }
};
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

5、电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution {
public:
    string hash[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> ret;
    string path;
    vector<string> letterCombinations(string digits) {
        if(digits.empty())
            return ret;
        dfs(digits,0);
        return ret;
    }
    void dfs(string digits,int pos)
    {
        if(pos==digits.size())
        {
            ret.push_back(path);
            return;
        }
        for(auto a : hash[digits[pos]-'0'])
        {
            path.push_back(a);
            dfs(digits,pos+1);
            path.pop_back();
        }
    }
};
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

6、括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

class Solution {
public:
    int left,right,n;
    vector<string> ret;
    string path;
    vector<string> generateParenthesis(int _n) {
        n=_n;
        dfs();
        return ret;
    }
    void dfs()
    {
        if(right==n)
        {
            ret.push_back(path);
            return;
        }

        if(left<n)
        {
            path.push_back('(');
            left++;
            dfs();
            path.pop_back();
            left--;
        }
        if(right<left)
        {
            path.push_back(')');
            right++;
            dfs();
            path.pop_back();
            right--;
        }
    }
};
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