本文共 3826 字，大约阅读时间需要 12 分钟。

                                               子集

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

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

示例:

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

输出:

[

  [3],

  [1],

  [2],

  [1,2,3],

  [1,3],

  [2,3],

  [1,2],

  []

]

public static List
   
    
     > subsets(int[] nums) {    List
     
      
       > res = new ArrayList<>();    backtrack(0, nums, res, new ArrayList
       
        ());    return res;}private static void backtrack(int i, int[] nums, List
        
         
          > res, ArrayList
          
            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
   
    
     > subsets(char[] chars) {        List
     
      
       > res = new ArrayList<>();        backtrack(0, chars, res, new ArrayList<>());        return res;    }    private static void backtrack(int i, char[] chars, List
       
        
         > res, ArrayList
         
           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的组合时，可以将原问题拆分为两个子问题：

public static void main(String[] args) {    char[] str = {'a','b'};    ArrayList
   
     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
    
      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);    }}

转载地址：http://htczz.baihongyu.com/