【算法专题】组合与排列

2022-03-16 2024-04-09 约 2700 字预计阅读 6 分钟

组合-求集合

无重复元素

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

回溯写法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int u) {
        res.push_back(path);
        for (int i = u; 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


class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int u) {
        // 递归至最后一个返回结果
        if (u == nums.size()) {
            res.push_back(path);
            return;
        }
        // 不选择当前数
        dfs(nums, u + 1);
        // 选择当前数
        path.push_back(nums[u]);
        dfs(nums, u + 1);
        // 复原
        path.pop_back();
    }
};

二进制枚举

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> path;
        int n = nums.size();
        for (int i = 0; i < (1 << n); i++) {
            path.clear();
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) path.push_back(nums[j]);
            }
            res.push_back(path);
        }
        return res;
    }
};

有重复元素

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

回溯 + sort：去重的是同一树层上“使用过”的节点，同一树枝路径上的都是一个组合里的元素，不用去重

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return res;
    }
    void dfs(vector<int>& nums, int u) {
        res.push_back(path);
        for (int i = u; i < nums.size(); i++) {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
            // 去重
            while (i + 1 < nums.size() && nums[i + 1] == nums[i]) i++;
        }
    }
};

二进制枚举 + sort：若发现当前数字与上一个数相同，且没有选择上一个数，则可以跳过当前生成的子集

简单总结为：相同的元素集中选择前面的

 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


class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<int> path;
        for (int i = 0; i < (1 << n); i++) {
            path.clear();
            bool flag = true;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    // 判断重复
                    if (j && nums[j] == nums[j - 1] && !(i & 1 << (j - 1))) {
                        flag = false;
                        break;
                    }
                    path.push_back(nums[j]);
                }
            }
            if (flag) res.push_back(path);
        }
        return res;
    }
};

无重复元素+有限选择

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


class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }
    // cur: [1, n]
    void dfs(int n, int k, int cur) {
        if (path.size() == k) {
            res.push_back(path);
            return;
        }
        for (int i = cur; i <= n; i++) {
            path.push_back(i);
            dfs(n, k, 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


class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return res;
    }
    // cur: [1, n]
    void dfs(int n, int k, int cur) {
        // 剪枝（后续全选也不足k个则提前终止，不剪枝超时）
        if (path.size() + (n - cur + 1) < k) return;

        if (path.size() == k) {
            res.push_back(path);
            return;
        }
        // 不选择当前位置
        dfs(n, k, cur + 1);
        
        // 选择当前位置
        path.push_back(cur);
        dfs(n, k, cur + 1);
        path.pop_back();
    }
};

约束选择

17. 电话号码的字母组合 | Code

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
public:
    const vector<string> keyboard {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> res;
    string path;
    vector<string> letterCombinations(string digits) {
        if (digits == "") return res;
        dfs(digits, 0);
        return res;
    }
    void dfs(string digits, int cur) {
        if (cur == digits.size()) {
            res.push_back(path);
            return;
        }
        for (char c: keyboard[digits[cur] - '0']) {
            path = path + c;
            dfs(digits, cur + 1);
            path.pop_back();
        }
    }
};

组合-匹配和

从集合中取出一系列数，这些数和与目标相等。

无重复元素+可重复选择

39. 组合总和 | Code

（为什么 sort 可以方便剪枝）【】

 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>> ans;
    vector<int> comb;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // sort方便剪枝 7ms->3ms
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0);
        return ans;
    }
    void dfs(vector<int>& candidates, int target, int startIdx) {
        if (target < 0) return; // 剪枝
        if (target == 0) {
            ans.push_back(comb);
            return;
        }
        for (int i = startIdx; i < candidates.size(); i++) {
            comb.push_back(candidates[i]);
            // 可重复选第i个
            dfs(candidates, target - candidates[i], i);
            comb.pop_back();
        }
    }
};

有重复元素+不可重复选择

40. 组合总和 II | Code

 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


class Solution {
public:
    vector<vector<int>> ans;
    vector<int> comb;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // sort 后续需要去重
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0);
        return ans;
    }
    void dfs(vector<int>& candidates, int target, int startIdx) {
        if (target < 0) return; // 剪枝
        if (target == 0) {
            ans.push_back(comb);
            return;
        }
        for (int i = startIdx; i < candidates.size(); i++) {
            comb.push_back(candidates[i]);
            // 不能重复选第i个
            dfs(candidates, target - candidates[i], i + 1);
            comb.pop_back();
            // 去重
            while (i + 1 < candidates.size() && candidates[i + 1] == candidates[i]) {
                i++;
            }
        }
    }
};

无重复元素+不可重复选择+有限选择

无重复元素（只使用数字1到9），不能重复选择，限制选择的个数为 k 个

216. 组合总和 III | Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
public:
    vector<vector<int>> ans;
    vector<int> comb;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return ans;
    }
    void dfs(int k, int n, int start) {
        if (n < 0 || k < 0) return; // 剪枝
        if (n == 0 && k == 0) {
            ans.push_back(comb);
            return;
        }
        for (int i = start; i <= 9; i++) {
            comb.push_back(i);
            // 不能重复选第i个
            dfs(k - 1, n - i, i + 1);
            comb.pop_back();
        }
    }
};

排列-求集合

无重复元素

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


class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<int> st;
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size(); path.resize(n); st.resize(n);
        dfs(nums, 0);
        return ans;
    }
    void dfs(vector<int>& nums, int u) {
        if (u == nums.size()) {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (!st[i]) {
                st[i] = true;
                path[u] = nums[i];
                dfs(nums, u + 1);
                // 还原
                st[i] = false;
            }
        }
    }
};

有重复元素

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

回溯 + sort

 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>> ans;
    vector<int> path;
    vector<int> st;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int n = nums.size(); path.resize(n); st.resize(n);
        
        sort(nums.begin(), nums.end());
        dfs(nums, 0);

        return ans;
    }
    void dfs(vector<int>& nums, int u) {
        if (u == nums.size()) {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (!st[i]) {
                st[i] = true;
                path[u] = nums[i];
                dfs(nums, u + 1);
                // 还原
                st[i] = false;
                // 去重
                while (i + 1 < nums.size() && nums[i] == nums[i + 1]) i++;
            }
        }
    }
};

回溯+cnt[]：遍历 map 的 key 达到同一层不会取重复数字的目的

不含重复数字只需要两个状态，含重复数字则用 cnt[] 记录每个数字的使用次数

 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:
    vector<vector<int>> ans;
    unordered_map<int, int> cnt;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int n = nums.size();
        for (int x: nums) cnt[x]++;

        vector<int> path(n);
        dfs(nums, path, 0);

        return ans;
    }
    void dfs(vector<int>& nums, vector<int>& path, int u) {
        if (u == nums.size()) {
            ans.push_back(path);
            return;
        }
        for (auto& [k ,v]: cnt) {
            if (v != 0) {
                cnt[k]--;
                path[u] = k;
                dfs(nums, path, u + 1);
                // 还原
                cnt[k]++;
            }
        }
    }
};

字符串的排列：LCR 157. 套餐内商品的排列顺序

排列-匹配和

无重复元素+可重复选择

377. 组合总和 Ⅳ：给你一个由不同整数组成的数组 nums，和一个目标整数 target。请你从 nums 中找出并返回总和为 target 的元素组合的个数

顺序不同的序列被视作不同的组合

这里回溯会超时，可以使用完全背包 DP，而且因为要考虑组合的顺序所以需要先遍历容量 target。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<unsigned long> f(target + 1);
        f[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < n; j++) {
                if (i >= nums[j]) {
                    f[i] += f[i - nums[j]];
                }
            }
        }
        return f[target];
    }
};

相似题目：518. 零钱兑换 II 求总和数不考虑顺序

总结

重复元素的去重

同层剪枝：同一父节点下，选择各不相同的子节点

实现方式：

sort：取重复数的第一个，后续跳过
map[]：遍历 map 的 key 达到同一层不会取重复数字的目的

思考

首先理清递归结构，可通过递归树帮助思考
设置全局变量，注意递归调用后复原
进入下一层，下标从哪开始？
- 组合：下标是递增的，不会从头考虑（当可重复选择时，下标从当前节点继续）
- 排列：下标每次从 0 开始，排列需要选择所有数据，前面没选后面可以继续选，使用额外的标记（st[] or cnt[]）记录选择情况
求集合时不会重复选择，匹配和会考虑重复选择的问题
其他相关题目：491. 非递减子序列

Reference

回溯算法入门级详解 + 练习

收录于合集・算法笔记 14

【算法专题】铺瓷砖【算法专题】快慢指针的应用