剑指offer Leetcode 排列、组合、子集总结

2024-02-03 13:41:46

回溯模板：

●画出树状图，横向遍历通过for循环实现，竖向遍历通过递归来实现。

●排列用visited来去重，组合和子集用start来去重

class Solution {
public:
    vector<vector<int>>ans;
    vector<vector<int>> func() {
        vector<int>path;
        backtrack(...);
        return ans;
    }

    void backtrack(...){
        if(结束条件){
            ans.push_back(path);
            return;
        }
        for(遍历起点){
            做选择，加入路径
            backtrack(...);
            撤销选择，撤销路径
        }

排列：

概念：

[1,2,3]的排列为[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

46题全排列

排列用visited来去重

也可以用交换法

class Solution {
public:
    vector<vector<int>>ans;
    int n;
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();    //不要写成int n = nums.size();
        if(n == 0)
            return {};
        vector<int>visited(n, 0);
        vector<int>tmp;
        backtrack(nums,visited, tmp);
        return ans;
    }
    
	// index可以不用，直接用tmp.size()
    void backtrack(vector<int>& nums, vector<int>&visited, vector<int>& tmp){
        // 都遍历完后到这里，推入答案
        if(tmp.size() == n)
            ans.push_back(tmp);
        // 如果未访问过，访问
        for(int i = 0; i < n; ++i){
            if(!visited[i]){
                tmp.push_back(nums[i]);
                visited[i] = 1;
                backtrack(nums, visited, tmp);
                visited[i] = 0;
                tmp.pop_back();
            }
        }
    }
};

47题：全排列II

在46题的基础上多了一个去重，即输入数组可能有重复。

去重两步骤：

●原函数中sort排序

●因为是去除同一层级的重复，所以使用以下代码：

// visited是用来解决一个分支即不同层级的重复，同一层级时visited为0才说明已经访问完了
if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])
	continue;

class Solution {
public:
    vector<vector<int>>ans;
    int n;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();    //不要写成int n = nums.size();
        if(n == 0)
            return {};
        sort(nums.begin(),nums.end());
        vector<int>visited(n, 0);
        vector<int>tmp;
        backtrack(nums, visited, tmp);
        return ans;
    }

    void backtrack(vector<int>& nums, vector<int>&visited, vector<int>& tmp){
        // 都遍历完后到这里，推入答案
        if(tmp.size() == n)
            ans.push_back(tmp);
        // 如果未访问过，访问
        for(int i = 0; i < n; ++i){
            if(!visited[i]){
                // 下面两行是添加的去重，需要先排序
                if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])
                    continue;
                tmp.push_back(nums[i]);
                visited[i] = 1;
                backtrack(nums, visited, tmp);
                visited[i] = 0;
                tmp.pop_back();
            }
        }
    }
};

组合：

概念：

[1,2,3]中2个数的组合[1,2] [1,3] [2,3]

注意：

●使用start来进行遍历

●backtrack()中要写i，不要写成start

●可用重复的是backtrack(i)，不可用是backtrack(i +1)

77.组合

用start的原因

想一下组合的过程，如[1,2,3]选2个数，顺序是12、13、23，都是选完前面的选后面的

class Solution {
public:
    vector<vector<int>>ans;
    vector<vector<int>> combine(int n, int k) {
        if(n < 1 || k < 0 || n < k)
            return {};
        vector<int>visited(n, 0);
        vector<int>path;
        backtrack(n, k, 1, path);
        return ans;
    }

    void backtrack(int n, int k, int start, vector<int>& path){
        // 当路径中有k个数时，返回
        if(path.size() == k){
            ans.push_back(path);
            return;
        }
        // 遍历可能的搜索起点，这里i的上限可以从n优化至n - (k - path.size()) + 1，因为是选择起点，所以剩下的元素个数是k - path.size()，所以上限是n - 个数 + 1
        for(int i = start; i <= n - (k - path.size()) + 1; ++i){
            // 推入路径
            path.push_back(i);
            // 进入下一轮，从i + 1开始，因为不能重复
            backtrack(n, k, i + 1, path);
            // 撤销操作
            path.pop_back();
        }
    }
};

39.组合总和

class Solution {
public:
    vector<vector<int>>ans;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int>path;
        backtrack(candidates, target, 0, 0, path);
        return ans;
    }

    void backtrack(vector<int>& candidates, int target, int start, int sum, vector<int>& path){
        if(sum == target){
            ans.push_back(path);
            return;
        }
        // 因为candidates中都是正数，所以大了可以直接返回
        if(sum > target)
            return;
        // 遍历可能的起点
        for(int i = start; i < candidates.size(); ++i){
            sum += candidates[i];
            path.push_back(candidates[i]);
            // 可以重复选择，所以为i
            backtrack(candidates, target, i, sum, path);
            sum -= candidates[i];
            path.pop_back();
        }
    }
};

40.组合总和II

与上一题的区别在于，候选数组有重复，解集不能重复选取

//在上一题基础上加上去重两步骤：1.sort 2.循环内部去重
sort(...);

//for循环是用来遍历同一层级的，要在同一层级上去重，就用下面的代码
if(i > start && candidates[i] == candidates[i - 1])
	continue;

216.组合总和III

就是起点为1，终点为9而已，没什么区别

子集：

概念：

[1,2]的子集为[],[1],[2],[1,2]

注意：

●子集每个过程都推入，即结束条件恒为1

78.子集

class Solution {
public:
    vector<vector<int>>ans;
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int>path;
        backtrack(nums, 0, path);
        return ans;
    }

    void backtrack(vector<int>& nums, int start, vector<int>& path){
        // 每个过程都推入
        ans.push_back(path);
        for(int i = start; i < nums.size(); ++i){
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path);
            path.pop_back();
        }
    }
};

90.子集II

即上一题的基础上加了去重，和组合的去重一模一样

sort();
...
if(i > start && nums[i] == nums[i - 1])
	continue;

码农公寓