题目1：字符串子序列（算法课第八课）

求一个字符串的全部子序列。

思路

不是子字符串。

对于每一个位置，都有要和不要的两种情况，最后是一个树状的图。

子序列不包含 当前字符

1. i作为String进行的哪里的做坐标，加1
2. res 保持原来的值

printAllSubsquence(chs,i+1,res)

子序列包含 当前字符

1. i作为String进行的哪里的做坐标，加1
2. res 加上当前字符

printAllSubsquence(chs,i+1,res+chs[i])

代码

public class PrintAllSubsquences{
    public static void printAllSubsquence(String str) {
        char[] chs = str.toCharArray();
        printAllSubsquence(chs, 0,"");
    }
    
    public static void printAllSubsquence(char[] chs,int i,String res) {
        if(i==chs.length) {
            System.out.println(res);
            return;
        }
        printAllSubsquence(chs,i+1,res);
        printAllSubsquence(chs,i+1,res+chs[i]);
    }
    
    public static void main(String[] args) {
        String test = "abc";
        printAllSubsquence(test);
    }
}

输出：(空字符串也是其子序列)

c
b
bc
a
ac
ab
abc

题目2：数组的和（算法课第八课）

给你一个数组arr，和一个整数aim。如果可以任意选择arr中的数字，能不能累加得到aim，返回true或者false

分析

每个数组位置的元素，都有选和不选两种情况。

没有累加i位置的元素

1. i作为数组进行的哪里的做坐标，加1
2. sum 保持原来的值

isSum(arr, i + 1, sum, aim)

累加了i位置的元素

1. i作为数组进行的哪里的做坐标，加1
2. sum 加上当前的 数组值

isSum(arr, i + 1, sum + arr[i], aim)

代码

public class IsSum {
    public static void main(String[] args) {
        int[] arr = new int[] { 1, 4, 8 };
        System.out.println(isSum(arr, 0, 0, 12));
    }

    public static boolean isSum(int[] arr, int i, int sum, int aim) {
        if (i == arr.length) {
            return sum == aim;
        }
        return isSum(arr, i + 1, sum, aim) || isSum(arr, i + 1, sum + arr[i], aim);
    }
}

输出：

true