DFS

LC46. Permutations

给一个包含不重复元素的数组，返回所有不同的排列

分析：用dfs枚举，用一个数组 vis 记录某个元素是否已经被使用，使用的时候 vis[i] = 1 ，回溯的时候 vis[i] = 0 ，用 idx 记录当前排列要放数据的位置

class Solution {
public:
    vector<int> nu, vis, cur;
    vector<vector<int>> res;
    int n;
    void dfs(int idx) {
        if (idx == n) {
            res.push_back(cur);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (vis[i]) continue;
            vis[i] = 1;
            cur[idx] = nu[i];
            dfs(idx + 1);
            vis[i] = 0;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        if (!n) return res;
        nu = nums;
        vis.assign(n, 0);
        cur.assign(n, 0);
        dfs(0);
        return res;
    }
};

 还有一种方法，还是dfs枚举，每次按序交换两个元素的位置

class Solution {
public:
    vector<vector<int>> res;
    int n;
    void dfs(vector<int>& nums, int begin) {
        if (begin == n) {
            res.push_back(nums);
            return;
        }
        for (int i = begin; i < n; ++i) {
            swap(nums[begin], nums[i]);
            dfs(nums, begin + 1);
            swap(nums[begin], nums[i]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        n = nums.size();
        dfs(nums, 0);
        return res;
    }
};

 LC47. Permutations II

给一个包含重复元素的数组，返回所有不同的排列

方法一：dfs枚举的时候，如果当前数字和前一个数字相等，且前一个数字没有被使用，那么当前数字也不会用

class Solution {
public:
    vector<int> cur, nu, vis;
    vector<vector<int>> res;
    int n;
    void dfs(int idx) {
        if (idx == n) {
            res.push_back(cur);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (vis[i]) continue;
            if (i > 0 && nu[i] == nu[i - 1] && !vis[i - 1]) continue;
            vis[i] = 1;
            cur[idx] = nu[i];
            dfs(idx + 1);
            vis[i] = 0;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        if (!n) return res;
        nu = nums;
        sort(nu.begin(), nu.end());
        cur.assign(n, 0);
        vis.assign(n, 0);
        dfs(0);
        return res;
    }
};

 方法二：用一个 cnt 数组记录每个数字出现的次数，因为数据没有给范围，所以 cnt[i] 记录每个 nu[i] 出现的次数，即记录下标，原数组需要去重并统计出现次数

class Solution {
public:
    vector<int> nu, cnt, cur;
    vector<vector<int>> res;
    int m, n;
    void dfs(int idx) {
        if (idx == n) {
            res.push_back(cur);
            return;
        }
        for (int i = 0; i < m; ++i) {
            if (cnt[i] == 0) continue;
            cnt[i]--;
            cur[idx] = nu[i];
            dfs(idx + 1);
            cnt[i]++;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        if (!n) return res;
        sort(nums.begin(), nums.end());
        int i = 0, j = 0;
        m = 0;
        while (i < n) {
            nu.push_back(nums[i]);
            cnt.push_back(1);
            j = i + 1;
            while (j < n && nums[j] == nums[i]) {
                cnt[m]++;
                j++;
            }
            i = j;
            m++;
        }
        cur.assign(n, 0);
        dfs(0);
        return res;
    }
};

 方法三：dfs + 交换元素，这种方法较难理解，不具有普遍性，dfs的数组参数是传值而不是传引用

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        help(nums, 0, result);
        return result;
    }
    
    void help(vector<int> nums, int begin, vector<vector<int>>& result) {
        if (begin == nums.size() - 1) {
            result.push_back(nums);
            return;
        }
        for (int i = begin; i < nums.size(); ++i) {
            if (i != begin && nums[i] == nums[begin]) continue;
            else {
                swap(nums[i], nums[begin]);
                help(nums, begin + 1, result);
            }
        }
    }
};