LeetCode刷题笔记 回溯算法

46 全排列 (opens new window)

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

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

解析：

class Solution {
public:
    void bt(vector<int>& nums, int level, vector<vector<int>>& ans){
        if(level==nums.size()-1){
            ans.push_back(nums);
            return;
        }
        for(int i=level;i<nums.size();++i){
            swap(nums[i],nums[level]);
            bt(nums,level+1,ans);
            swap(nums[i],nums[level]);
        }
        return;
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        bt(nums,0,ans);
        return ans;
    }
};

47 全排列 II (opens new window)

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

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

解析：

class Solution {
public:
    void bt(vector<int>& nums, int level, vector<vector<int>>& ans){
        if(level==nums.size()-1){
            ans.push_back(nums);
            return;
        }
        for(int i=level;i<nums.size();++i){
            sort(nums.begin()+level,nums.end());
            if(i>level && nums[i]==nums[i-1]){
                continue;
            }
            swap(nums[i],nums[level]);
            bt(nums,level+1,ans);
            swap(nums[i],nums[level]);
        }
        return;
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        bt(nums,0,ans);
        return ans;
    }
};

剑指 Offer 38 字符串的排列 (opens new window)

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

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

解析：

class Solution {
public:
    void bt(string s, int level, vector<string>& ans){
        if(level == s.length()-1){
            ans.push_back(s);
            return;
        }
        unordered_set<char> set;
        for(int i=level;i<s.length();++i){
            if(set.count(s[i])){
                continue;
            }
            set.insert(s[i]);
            swap(s[i],s[level]);
            bt(s,level+1,ans);
            swap(s[i],s[level]);
        }
        return;
    }

    vector<string> permutation(string s) {
        vector<string> ans;
        bt(s,0,ans);
        return ans;
    }
};