NC121—字符串的排列

题意

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abcacbbacbcacabcba

题解

class Solution {
public:
    vector<string> Permutation(string str) {
        if(str.empty()) return {};
        set<string> res;
        backtrack(str, 0, res);
        return vector<string>({res.begin(), res.end()});
    }
    
    void backtrack(string str, int pos, set<string>& res){
        if(pos == str.size() - 1){
            res.insert(str);
            return;
        }
        
        for(int i = pos; i < str.size(); i++){
            swap(str[pos], str[i]);
            backtrack(str, pos+1, res);
            swap(str[pos], str[i]);
        }
    }
};
上一篇:LeetCode 37. 解数独


下一篇:算法设计-01背包子集树的递归写法