LeetCode--子集（回朔法）

子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]

输出:

[

[3],

[1],

[2],

[1,2,3],

[1,3],

[2,3],

[1,2],

[]

]

public static List<List<Integer>> subsets(int[] nums) {

    List<List<Integer>> res = new ArrayList<>();

    backtrack(0, nums, res, new ArrayList<Integer>());

    return res;



}



private static void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {

    res.add(new ArrayList<>(tmp));

    for (int j = i; j < nums.length; j++) {

        tmp.add(nums[j]);

        backtrack(j + 1, nums, res, tmp);

        tmp.remove(tmp.size() - 1);

    }

}

剑指字符组合

输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

上面我们详细讨论了如何用递归的思路求字符串的排列。同样，本题也可以用递归的思路来求字符串的组合。

假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：第一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；第二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码：

最简单的思路把加的条件取消

public class subsets {
    public static void main(String[] args) {
        char[] str = {'a','b','c'};
        subsets(str);
    }
    public static List<List<Character>> subsets(char[] chars) {
        List<List<Character>> res = new ArrayList<>();
        backtrack(0, chars, res, new ArrayList<>());
        return res;

    }

    private static void backtrack(int i, char[] chars, List<List<Character>> res, ArrayList<Character> tmp) {
        res.add(new ArrayList<>(tmp));
        for (int j = i; j < chars.length; j++) {
            tmp.add(chars[j]);
            backtrack(j + 1, chars, res, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}

解题思路书上

个字符中选择m的组合时，可以将原问题拆分为两个子问题：
1）如果组合里包含第一个字符，则在剩下的n-1个中选择m-1个字符；
2）如果组合里不包含第一个字符，则在剩下的n-1个中选择m个字符；

public static void main(String[] args) {
    char[] str = {'a','b'};
    ArrayList<Character> result = new ArrayList<>();
    for (int i = 1;i <= str.length;i++)
    {
        Combination(str,0,i,result);
        //从数组中第一个字符开始，依次取num个，num >=1 && num <= 数组长度
    }
}
public static void Combination(char[] str,int begin, int num, ArrayList<Character> result){
    if (str == null || str.length == 0) {
        //注意：begin > str.length - 1这个条件不能放在这里一起判断
        // 因为有时候当num为0的时候，begin也满足begin>str.len-1，但是这时候我们已经在result中的字符是一种组合，应该保证先输出再返回
        return;
    }
    if (num == 0){
        //如果num为0,说明已经凑够了num个字符，直接输出并返回
        System.out.println(result);
        return;
    }
    if (begin > str.length-1)
    {
        return;
    }
    result.add(str[begin]);
    //当前的字符被选中
    Combination(str,begin+1,num-1,result);
    //则从索引位置为begin+1的位置开始选择剩下的num-1个字符
    result.remove(result.size()-1);
    //当前的字符未被选中
    Combination(str,begin+1,num,result);
    //则从索引位置为begin+1的位置继续选择num个字符
}

public static void main(String [] args)
{
    String str = "abc";
    multiCombination(str);
}
public static void multiCombination(String str)
{
    if (null == str)
    {
        return ;
    }

    StringBuilder sb = new StringBuilder();
    int iter = 1;
    while (iter <= str.length())
    {
        multiCombination(str, iter, sb);
        ++iter;
    }
}
private static void multiCombination(String str, int m, StringBuilder sb)
{
    if (m == 0)
    {
        System.out.println(sb.toString());
        return ;
    }
    if (str.length() != 0)
    {
        sb.append(str.charAt(0));
        // 从剩余的n-1个中选择m-1个
        multiCombination(str.substring(1), m - 1, sb);
        sb.deleteCharAt(sb.length() - 1);
        // 从剩余的n-1个中选择m个
        multiCombination(str.substring(1), m, sb);
    }
}

public static void main(String[] args) {
    combine("abc");
}
private static void combine(String str) {
    char[] in = str.toCharArray();
    StringBuffer out = new StringBuffer();
    allCombine(in, out, 0);
}

private static void allCombine(char[] in, StringBuffer sb, int start) {
    for (int i = start; i < in.length; i++) {
        sb.append(in[i]);
        System.out.println(sb);
        if (i < in.length - 1)
        {
            allCombine(in, sb, i + 1);
        }
        sb.setLength(sb.length() - 1);
    }
}