回溯法：排列

0046. 全排列 (opens new window)

题目

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

解析

回溯法，维护两个数组，分别记录当前排列和每个数字的使用情况，之后枚举每个位置可能出现的数字即可。

代码

class Solution {
    vector<vector<int>> ans;
    vector<int> combine;
    vector<bool> used;
public:
    vector<vector<int>> permute(vector<int>& nums) {
        used = vector<bool>(nums.size());
        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int idx) {
        if (idx == nums.size()) {
            ans.push_back(combine);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (!used[i]) {
                combine.push_back(nums[i]);
                used[i] = true;
                dfs(nums, idx + 1);
                used[i] = false;
                combine.pop_back();
            }
        }
    }
};

0047. 全排列 II (opens new window)

题目

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

解析

本题与 0046. 全排列 类似，要去除不重复排列，只需要保证重复元素的相对顺序不变，即按序使用重复元素。

因此，在循环时增加判断前一个相等元素是否被使用，如果未被使用说明是乱序，跳过即可。

代码

class Solution {
    vector<vector<int>> ans;
    vector<int> combine;
    vector<bool> used;
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        used = vector<bool>(nums.size());
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int idx) {
        if (idx == nums.size()) {
            ans.push_back(combine);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (!used[i]) {
                if (i && nums[i - 1] == nums[i] && !used[i - 1]) continue;
                combine.push_back(nums[i]);
                used[i] = true;
                dfs(nums, idx + 1);
                used[i] = false;
                combine.pop_back();
            }
        }
    }
};