题解 | #字符串的全部子序列#

import java.util.*;

/**
 * NC190 字符串的全部子序列
 * @author d3y1
 */
public class Solution {
    // 哈希
    private HashSet<String> set = new HashSet<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串一维数组
     */
    public String[] generatePermutation (String s) {
        return solution1(s);
        // return solution2(s);
    }

    /**
     * 递归 + 哈希
     * @param s
     * @return
     */
    private String[] solution1(String s){
        dfs(s, 0, "");
        ArrayList<String> list = new ArrayList<>(set);
        return list.toArray(new String[list.size()]);
    }

    /**
     * 递归
     * @param s
     * @param idx
     * @param sub
     */
    private void dfs(String s, int idx, String sub){
        set.add(sub);
        if(idx == s.length()){
            return;
        }
        // 从左往右 依次选择
        for(int i=idx; i<s.length(); i++){
            dfs(s, i+1, sub+s.charAt(i));
        }
    }

    /**
     * 递归 + 哈希
     * @param s
     * @return
     */
    private String[] solution2(String s){
        operate(s, 0, "");
        ArrayList<String> list = new ArrayList<>(set);
        return list.toArray(new String[list.size()]);
    }

    /**
     * 递归
     * @param s
     * @param idx
     * @param sub
     */
    private void operate(String s, int idx, String sub){
        set.add(sub);
        if(idx == s.length()){
            return;
        }
        // 选择
        operate(s, idx+1, sub+s.charAt(idx));
        // 不选
        operate(s, idx+1, sub);
    }
}