获取字符串的所有子序列
 子序列：字符的相对位置不变，但可以选要与不要
 打印所有子序列：从左往右依次的尝试模型
 从第一个字符开始做决定，选择要与不要
 eg:
 a b c
 0 1 2
 0: 要a,不要a
1:要b ,不要b
 2:要c ,不要c
"",a,ab,ac,abc,b,bc,c

暴力递归：

  public List<String> allSubSeq(String str){
        List<String> ans=new ArrayList<>();
        if(str==null){
            return ans;
        }
        if(str.length()==0){
            ans.add("");
            return ans;
        }
        char[] chs=str.toCharArray();
        process(chs,0,"",ans);
        return ans;
    }

    /**
     ans: 收集的结果集
     path:记录沿途的路径
     str[0....index-1]的沿途决定，是path记录的
     str[index...]的每一个字符，都可以选择要与不要
     所以的子序列，都放入到ans里去
     */
    private void process(char[] str,int index,String path,List<String> ans){
        if(index==str.length){
            ans.add(path);
            return;
        }
        //不要当前字符
        process(str,index+1,path,ans);
        //要当前字符
        process(str,index+1,path+str[index],ans);
    }

　　

115. 不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。

（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

暴力递归的方式在leetcode会超出空间限制，这里先给出暴力递归的代码，后面优化成动态规划或缓存优化

class Solution {
    public int numDistinct(String s, String t) {
       List<String> ans= getAllSubseq(s);
       int index=0;
          for(String str:ans){
              if(str.equals(t)){
                    index++;
              }
           
        }
        return index;
    }

    public List<String> getAllSubseq(String str){
        List<String> ans=new ArrayList<>();
        if(str==null){
            return ans;
        }
        if(str.length()==0){
            ans.add("");
            return ans;
        }
        char[] chs=str.toCharArray();
        process(chs,0,"",ans);
      
      
        return ans;
    }

    public void process(char[] chs,int index,String path,List<String> ans){
        //base case
        if(index==chs.length){
            ans.add(path);
            return;
        }
        process(chs,index+1,path,ans);
        process(chs,index+1,path+chs[index],ans);
    }
}