lintcode--17. 子集

描述

给定一个含不同整数的集合，返回其所有的子集

注意事项

子集中的元素排列必须是非降序的，解集必须不包含重复的子集

样例

如果 S = [1,2,3]，有如下的解：

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

代码

import java.util.*;
public class Solution {

    /*
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> result=new ArrayList<>();
        if(nums==null){
            return null;
        }
        Arrays.sort(nums);
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<=nums.length;i++){ //这里i的值代表子串长度的可能值，0代表空，直到子串的长度为nums的长度
            list.clear();
            core(nums,0,i,list,result);
        }
        return result;
    }
    /**
     * 
     * @param nums 
     * @param start 数组当前的索引
     * @param size 当前指定的子串的长度
     * @param list 用于保存某个子串
     * @param result 
     */
    void core(int[] nums,int start,int size,List<Integer> list,List<List<Integer>> result){
        if(list.size()==size){  //判断当前子串的长度是否和指定的长度相同
            result.add(new ArrayList<>(list));
        }else{
            for(int i=start;i<nums.length;i++){
                list.add(nums[i]);   //向list添加当前子串的元素           
                core(nums,i+1,size,list,result);
                list.remove(list.size()-1);//移除第一步添加的元素
            }
        }

    }
}