组合排列——回溯法的实践

2023-11-02

一、模板

对于回溯问题，可以给一个模板

result = []

def backtracking(参数)
 {
     if (终止条件) {
         result.add(路径)
         return;
     }

     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
         处理节点;
         backtracking(路径，选择列表);  // 递归
         回溯，撤销处理结果
     }
 }

二、46题全排列

2.1 题目

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

2.2 解析

这个问题可以看作有 n个排列成一行的空格，我们需要从左往右依此填入题目给定的 n 个数，每个数只能使用一次。那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n 个空格，在程序中我们可以用「回溯法」来模拟这个过程。

我们定义递归函数 backtrack(first, output) 表示从左往右填到第 first 个位置，当前排列为 output。那么整个递归函数分为两个情况：

如果 first==n，说明我们已经填完了 n个位置（注意下标从 0 开始），找到了一个可行的解，我们将 output 放入答案数组中，递归结束。
如果 first<n，我们要考虑这第 first 个位置我们要填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组 vis[] 来标记已经填过的数，那么在填第 first 个数的时候我们遍历题目给定的 n 个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(first + 1, output)。回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。

2.3 代码

class Solution {

public: // dfs + 回溯
    int len;
    vector<bool> status; // 记录是否选择过
    vector<vector<int>> ret; // 最终的路径数组
    vector<int> track;
    void backTrack(vector<int> &nums)
    {
        if (track.size() == len) { // 满足长度，直接返回
            ret.push_back(track);
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!status[i]) {
                status[i] = true;
                track.push_back(nums[i]);
                backTrack(nums);
                track.pop_back();
                status[i] = false;
            }
        }
    }

    vector<vector<int>> permute(vector<int> &nums)
    {
        len = nums.size();
        status.resize(len, false); // 初始化，都没使用过
        backTrack(nums);
        return ret;
    }
};

三、78题子集

3.1 题目

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

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

3.2 解析

直接套公式

3.3 代码

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
        if (startIndex >= nums.size()) { // 终止条件可以不加
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

四、39题组合

4.1 题目

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

4.2 解析

使用模板，搜索回溯

4.3 代码

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int> &candidates, int target, int sum, int startIndex)
    {
        if (sum > target) {
            return;
        }
        if (sum == target) { // 满足结束条件
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i < candidates.size(); i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i);  // 不用i+1了，表示可以重复读取当前的数
            sum -= candidates[i];
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        result.clear();
        path.clear();
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

参考：

力扣

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)