程序员面试金典 - 面试题 08.07. 无重复字符串的排列组合（回溯）

示例1:
 输入：S = "qwe"
 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
 
示例2:
 输入：S = "ab"
 输出：["ab", "ba"]
 
提示:
字符都是英文字母。
字符串长度在[1, 9]之间。

class Solution {
	vector<string> ans;
	int n;
public:
    vector<string> permutation(string S) {
    	n = S.size();
    	vector<bool> visited(n,false);
    	dfs(S,"",0, visited);
		return ans;
    }

    void dfs(string& S, string t, int count, vector<bool>& visited)
    {
    	if(count==n)
    	{
    		ans.push_back(t);
    		return;
    	}
    	for(int i = 0; i < n; ++i)
    	{
    		if(!visited[i])
    		{
    			t.push_back(S[i]);
    			visited[i] = true;
    			dfs(S,t,count+1,visited);
    			t.pop_back();
    			visited[i] = false;
    		}
    	}
    }
};