前言

今天下午跟晚上有事耽搁了，不过早上还是做了蛮多回溯题的。

题目

46 全排列 I

题目

全排列 I

思路

直接暴力dfs就好了，注意回溯的条件。

代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> ans;
    bool check[30];
    vector<vector<int>> permute(vector<int>& nums) {
        int len = nums.size();
        ans.resize(len);
        dfs(0, nums);
        return res;
    }
    void dfs(int index, vector<int>& nums){
        if(index == nums.size()){
            res.emplace_back(ans);
        }
        for(int i = 0; i < nums.size(); ++ i){
            if(!check[i]){
                ans[index] = nums[i];
                check[i] = true;
                dfs(index + 1, nums);
                check[i] = false;
            }
        }
    }
};

47 全排列 II

题目

全排列 II

思路

主要是数组内有重复的元素，通过观察可知，只要相等的元素相对的顺序不变即可。

代码

class Solution {
public:
    vector<vector<int> > res;
    vector<int> ans;
    bool check[25];
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int len = nums.size();
        ans.resize(len);
        sort(nums.begin(), nums.end());
        dfs(0, nums);
        return res;
    }
    void dfs(int index, vector<int>& nums){
        if(index == nums.size()){
            res.emplace_back(ans);
            return;
        }
        for(int i = 0; i < nums.size(); ++ i){
            if(i && nums[i] == nums[i - 1] && !check[i - 1]) continue;//按照数位来查找
            if(!check[i]){
                ans[index] = nums[i];
                check[i] = true;
                dfs(index + 1, nums);
                check[i] = false;
            }
        }
    }
};