字符串的全部子序列

public static String[] generatePermutation (String s) {
        // write code here
        Set<String> set = new HashSet<>();
        set.add("");
        char[] chars = s.toCharArray();
        for (char c : chars) {
            ArrayList<String> strings = new ArrayList<>(set);
            for (String str : strings) {
                str += c;
                set.add(str);
            }
        }
        return set.toArray(new String[0]);
    }

class Solution:
    def generatePermutation(self , s: str) -> List[str]:
        # write code here
        res = set()
        res.add("")
        def f(s, index, res, path):
            if index >= len(s):
                return 
            
            # 当前字符要
            res.add(path+s[index])
            f(s, index + 1, res, path+s[index])
            # 当前字符不要
            res.add(path)
            f(s, index + 1, res, path)
        f(s,0,res, '')
        return list(res)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串一维数组
     */
    public String[] generatePermutation (String s) {
        // write code here
        HashSet<String> set=new HashSet<>();
        char arr[]=s.toCharArray();
        dfs(arr,new StringBuilder(),0,set);
        String str[]=set.toArray(new String[set.size()]);
        return str;
        
    }
    public void dfs(char[] arr,StringBuilder sb,int index,HashSet<String> set){
        set.add(sb.toString());
        for(int i=index;i<arr.length;i++){
            sb.append(arr[i]);
            dfs(arr,sb,i+1,set);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return string字符串一维数组
*/
func generatePermutation( s string ) []string {
    ans:=[]string{}
    vis:=map[string]bool{}
    var back_tracking func(string,int)
    back_tracking=func(path string,idx int){
        if _,ok:=vis[path];!ok{
            ans=append(ans,path)
            vis[path]=true
        }
        for i:=idx;i<len(s);i++{
            path+=string(s[i])
            back_tracking(path,i+1)
            path=path[:len(path)-1]
        }
    }
    back_tracking("",0)
    return ans
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    void recursion(const string& s, vector<string>& v, string s1, int index, int capacity){
        if(s1.length() == capacity && m.find(s1) == m.end()){
            m[s1]++;
            v.push_back(s1);
            return;
        }
        for(int i=index; i<s.length(); i++){
            s1.push_back(s[i]);
            recursion(s, v, s1, i+1, capacity);
            s1.pop_back();
        }
    }
    unordered_map<string, int> m;
    vector<string> generatePermutation(string s) {
        // write code here
        vector<string> v;
        string s1 = "";
        v.push_back(s1);
        for(int i=1; i<=s.length(); i++){
            recursion(s, v, s1, 0, i);
        }
        return v;
    }
};

public class Solution {
    public String[] generatePermutation (String s) {
        ArrayList<String> list = new ArrayList<>();
        char[] arr = s.toCharArray();
        process(arr,0,"",list);
        String result[] = new String[list.size()];
        int i=0;
        for(String e:list) {
        	result[i++] = e;
        }
        return result;
    }
    public void process(char arr[],int i,String str,ArrayList<String> list) {
    	if(i==arr.length) {
    		if(!list.contains(str)) {
    			list.add(str);
    		}
    		return;
    	}
    	process(arr,i+1,str,list);
    	process(arr,i+1,str+arr[i],list);
    }
}

class Solution:
    def generatePermutation(self , s: str) -> List[str]:
        a = [""]
        for c in s:
            a.extend([ x+c for x in a ])
        return list(set(a)) 

import java.util.*;

// 回溯比用位运算更好，毕竟是要成功率不是炫技
public class Solution {
    public String[] generatePermutation (String s) {
        backTrack(s.toCharArray(), 0);
        return res.toArray(new String[0]);
    }
    StringBuilder sb = new StringBuilder();
    HashSet<String> res = new HashSet<>();
    public void backTrack(char[] c, int idx) {
        if (!res.contains(sb.toString()))
            res.add(sb.toString());
        else return;
        for (int i = idx; i < c.length; i++) {
            sb.append(c[i]);
            backTrack(c, i+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串一维数组
     */
    public String[] generatePermutation (String s) {
        char[] chars = s.toCharArray();
        Set<String> res = new HashSet<>();
        StringBuilder builder = new StringBuilder();
        builder.append("");
        dfs(builder,chars,0,res);
        String[] strArr = new String[res.size()];
        int index = 0;
        for (String elem : res) {
            strArr[index++]=elem;
        }
        return strArr;
    }

    private void dfs(StringBuilder track,char[] chars,int depth,Set<String>res) {
        if (depth>=chars.length) {
            res.add(track.toString());
            return;
        }

        // 当前位置不选
        dfs(track,chars,depth+1,res);
        // 当前位置选择
        track.append(chars[depth]);
        dfs(track,chars,depth+1,res);
        track.delete(track.length()-1,track.length());
    }
}

import java.util.*;
public class Solution {
    public String[] generatePermutation (String s) {
        ArrayList<String> list=new ArrayList<>();
        printAllSub(s.toCharArray(), 0, "",list);
        String[] res=new String[list.size()];
        for(int i=0;i<res.length;i++){
            res[i]=list.get(i);
        }
        return res;
    }
    
    public static void printAllSub(char[] str, int i, String res,ArrayList<String> list) {
        if (i == str.length) {
            list.add(res);
            return ;
        } else {
            printAllSub(str, i + 1, res,list); // 不要下标为i+1的字符
            printAllSub(str, i + 1, res+str[i],list); // 要第i+1个字符
        }
    }
}