1.1 组合问题(不可重复)

了解一个典型例题，总结出回溯的模板。给定两个整数 n 和 k ，返回 1…n 中所有可能的 k 个数的组合。

示例：输入： n =4 ， k =2 输出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

给出如下解答：

class Solution{
private:
    //存放符合条件的path的集合
    vector<vector<int>> result;
    //可变路径
    vector<int> path;
    void backtracking(int n ,int k ,int satrtIndex){
        //当路径长度是k时，将路径加入结果集；
        if(path.size() == k){
            result.push_back(path);
            return;
        }
        //横向遍历
        for(int i = satrtIndex; i<=n; i++){
            path.push_back(i);
            backtracking(n,k,i+1);//递归，即纵向遍历
            path.pop_back();//回溯，撤销处理的节点
        }
    }
public:
    	vector<vector<int>> combine(int n,int k){
  
            backtracking(n, k, 1);
            return result;
            
        }
};

1.1 组合问题(可重复)

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

candidates 中的数字可以无限制重复被选取。如：

• 输入：candidates = [2,3,6,7], target = 7,
• 所求解集为： [ [7], [2,2,3] ]

class Solution {
private:
    // 定义 result 用于存放满足条件的组合
    vector<vector<int>> result;
    // 定义 path 用于存放当前尝试的组合
    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;
        }

        // 从 startIndex 开始遍历候选数组
        for (int i = startIndex; i < candidates.size(); i++) {
            // 将当前元素加入组合，并更新 sum
            sum += candidates[i];
            path.push_back(candidates[i]);
            // 继续回溯，使用 i 而非 i+1，表示可以重复读取当前的数
            backtracking(candidates, target, sum, i);
            // 回溯时，撤销上一步操作，恢复 sum 和 path 的状态
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    // 主函数，用于调用回溯函数求解组合总和问题
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // 调用回溯函数，初始 sum 为 0，初始 startIndex 为 0
        backtracking(candidates, target, 0, 0);
        // 返回结果
        return result;
    }
};

1.2 子集问题

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

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) {

        backtracking(nums, 0);
        return result;
    }
};

1.3 全排列问题

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) continue; // path里已经收录的元素，直接跳过
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
       
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};