排列组合问题（回溯法）.md

排列问题：[a, b, c] 和 [b, a, c] 是不同的排列，每一层回溯遍历时需要从 0n 遍历（可以通过 swap 的方式优化为不从 0 开始遍历）；如果有相同元素，需要记录每一层有哪些元素已经遍历过了，并在下一层选择时跳过。 组合问题：[a, b, c] 和 [b, a, c] 是同一个组合，每一层回溯遍历时从 kn，即遍历时从下一个元素即可

有重复元素的解决办法：

• 先排序，遍历的时候判断 N[i] == N[i - 1]就跳过
• 同一 level 用一个 set 记录选了哪些元素

排列问题

剑指 Offer 38. 字符串的排列

https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

限制： 1 <= s 的长度 <= 8

注意：字符串可能有重复字符需要做去重

解题思路： 排列方案数量： 对于一个长度为 n 的字符串（假设字符互不重复），其排列共有 n×(n−1)×(n−2)…×2×1 种方案。

排列方案的生成方法： 根据字符串排列的特点，考虑深度优先搜索所有排列方案。先选择第 1 位字符（ n 种情况）、再选择第 2 位字符（n−1 种情况）、... 、最后选择第 n 位字符（ 1 种情况）。     重复方案与剪枝： 当字符串存在重复字符时，排列方案中也存在重复方案。为排除重复方案，需在选择某位字符时，保证 “每种字符只在此位被选择一次” ，即遇到重复字符时直接跳过。从 DFS 角度看，此操作称为 “剪枝” 。    

更容易理解的解法：

class Solution {
public:
vector<string> permutation(string s) {
    vector<string> ret;
    string cur_ret;
    unordered_set<int> filter;
    backtracking(ret, cur_ret, s, filter);
    return ret;
}

// filter 用来保证不同层不能选同一个元素, 但是可以选相同的值, 因此记录的是 index 而不是 value
void backtracking(std::vector<string>& ret, string& cur_ret, const string& s, unordered_set<int>& filter) {
    if (cur_ret.length() == s.length()) {
        ret.push_back(cur_ret);
        return;
    }

    // 记录当前 level 选择了哪些元素，保证同一层不能选重复的元素
    std::unordered_set<char> sel;
    // 对当前层遍历所有元素
    for (int i = 0; i < s.length(); i++) {
        // 如果这个位置的元素已经在上层被选择过了，就不能再选择
        if (filter.count(i) > 0) continue;
        // 如果这个元素在当前 层 已经选过了，就不能再选择
        if (sel.count(s[i]) > 0) continue;
        // 注意 sel 在 backtracking 后不能 erase，因为其目的就是为了记录当前层哪些元素已经遍历过了
        sel.insert(s[i]);

        cur_ret.append(1, s[i]);
        filter.insert(i);
        backtracking(ret, cur_ret, s, filter);
        // 注意 filter 在 backtracking 返回后需要 erase，因为回到选择上一层了
        filter.erase(i);
        cur_ret = cur_ret.substr(0, cur_ret.length() - 1);
    }
  }
};

下面的解法是通过交换字符达到同样的结果：

class Solution {
public:
    vector<string> permutation(string s) {
        char* sc = s.data();
        vector<string> ret;
        backtracking(ret, sc, s.length(), 0);
        return ret;
    }

    void backtracking(vector<string>& ret, char* sc, int len, int index) {
        if (index == len - 1) {
            ret.emplace_back(sc);
            return;
        }

        unordered_set<char> filter; // 记录同一 level 哪些字符已经选过了
        for (int i = index; i < len; i++) {
            if (filter.count(sc[i]) > 0) continue; // 同一 level 相同字符就不能再选了
            filter.insert(sc[i]);
            swap(sc, index, i);
            backtracking(ret, sc, len, index+1); // 固定下一个位置(level)的字符
            swap(sc, index, i);
        }
    }

    void swap(char* sc, int i, int j) {
        char tmp = sc[i];
        sc[i] = sc[j];
        sc[j] = tmp;
    }
};

46. 全排列

https://leetcode.cn/problems/permutations/

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

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> cur;
        unordered_set<int> filter;
        backtracking(ret, cur, nums, filter);
        return ret;
    }

    void backtracking(vector<vector<int>>& ret, vector<int>& cur, const vector<int>& nums, unordered_set<int>& filter) {
        if (cur.size() == nums.size()) {
            ret.push_back(cur);
            return;
        }

        // 同一层可以选择的所有元素，注意 index 从 0 开始
        for (int i = 0 ; i < nums.size(); i++) {
            // 如果该位置的元素已经在上层选择过了，就跳过
            if (filter.count(i) > 0) continue;

            filter.insert(i);
            cur.push_back(nums[i]);
            backtracking(ret, cur, nums, filter);
            cur.pop_back();
            filter.erase(i);
        }
    }
};

通过交换元素位置达到相同效果：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        backtracking(ret, nums, 0);
        return ret;
    }

    void backtracking(vector<vector<int>>& ret, vector<int>& nums, int k) {
        if (k == nums.size()) {
            ret.push_back(nums);
            return;
        }

        for (int i = k ; i < nums.size(); i++) {
            swap(nums, k, i);
            backtracking(ret, nums, k + 1);
            swap(nums, k, i);
        }
    }

    void swap(vector<int>& nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};

47. 全排列 II

https://leetcode.cn/problems/permutations-ii/

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

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        vector<int> cur;
        vector<bool> vis;
        for (int i = 0; i < nums.size(); i++) vis.push_back(false);
        backtracking(ret, cur, nums, vis);
        return ret;
    }

    void backtracking(vector<vector<int>>& ret, vector<int>& cur, vector<int>& nums, vector<bool>& vis) {
        if (cur.size() == nums.size()) {
            ret.push_back(cur);
            return;
        }

        for (int i = 0 ; i < nums.size(); i++) {
            // for循环保证了从数组中从前往后一个一个取值，再用if判断条件。所以nums[i - 1]一定比nums[i]先被取值和判断。如果nums[i - 1]被取值了，那vis[i - 1]会被置1，只有当递归再回退到这一层时再将它置0。每递归一层都是在寻找数组对应于递归深度位置的值，每一层里用for循环来寻找。所以当vis[i - 1] == 1时，说明nums[i - 1]和nums[i]分别属于两层递归中，也就是我们要用这两个数分别放在数组的两个位置，这时不需要去重。但是当vis[i - 1] == 0时，说明nums[i - 1]和nums[i]属于同一层递归中（只是for循环进入下一层循环），也就是我们要用这两个数放在数组中的同一个位置上，这就是我们要去重的情况
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) continue;
            cur.push_back(nums[i]);
            vis[i] = true;
            backtracking(ret, cur, nums, vis);
            cur.pop_back();
            vis[i] = false;
        }
    }
};

组合问题

39. 组合总和

https://leetcode.cn/problems/combination-sum/

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。  对于给定的输入，保证和为 target 的不同组合数少于 150 个。  

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> cur;
        backtracking(ret, cur, candidates, target, 0);
        return ret;
    }

    void backtracking(vector<vector<int>>& ret, vector<int>& cur, vector<int>& candidates, int target, int start) {
        if (target < 0) return;
        if (target == 0) {
            ret.push_back(cur);
            return;
        }

        for (int i = start; i < candidates.size(); i++) {
            cur.push_back(candidates[i]);
            backtracking(ret, cur, candidates, target - candidates[i], i);
            cur.pop_back();
        }
    }
};

40. 组合总和 II

https://leetcode.cn/problems/combination-sum-ii/

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        std::sort(candidates.begin(), candidates.end());
        std::vector<std::vector<int>> ret;
        vector<int> cur;
        backtracking(ret, cur, candidates, target, 0);
        return ret;
    }

    void backtracking(vector<vector<int>>& ret, vector<int>& cur, vector<int>& candidates, int target, int start) {
        if (target == 0) {
            ret.push_back(cur);
            return;
        }
        if (target < 0) return;

        for (int i = start; i < candidates.size(); i++) {
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            cur.push_back(candidates[i]);
            backtracking(ret, cur, candidates, target - candidates[i], i+1);
            cur.pop_back();
        }
    }
};

78. 子集

https://leetcode-cn.com/problems/subsets/

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> cur_ret;
        backtracking(ret, cur_ret, nums, 0);
        return ret;
    }

    void backtracking(vector<vector<int>>& ret, vector<int>& cur_ret, const vector<int>& nums, int k) {
        ret.push_back(cur_ret);

        for (int i = k; i < nums.size(); i++) {
            cur_ret.push_back(nums[i]);
            backtracking(ret, cur_ret, nums, i + 1);
            cur_ret.pop_back();
        }
    }
};

90. 子集 II

https://leetcode-cn.com/problems/subsets-ii/

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        vector<int> cur_ret;
        backtracking(ret, cur_ret, nums, 0);
        return ret;
    }

    void backtracking(vector<vector<int>>& ret, vector<int>& cur_ret, const vector<int>& nums, int k) {
        ret.push_back(cur_ret);

        for (int i = k; i < nums.size(); i++) {
            if (i > k && nums[i] == nums[i - 1]) continue;
            cur_ret.push_back(nums[i]);
            backtracking(ret, cur_ret, nums, i + 1);
            cur_ret.pop_back();
        }
    }
};