78.子集

题目描述

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

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

示例：

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

思路

1.这道题可以使用回溯思想求解。
2.解题思路与77.组合类似，我们只需要进行0到n次组合计算即可。

Java代码实现

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i=0;i<=nums.length;i++){
            combine(res,nums,i);
        }
        return res;
    }

    private void combine(List<List<Integer>> res ,int[] nums, int k){
        combine(res,new ArrayList(),0,nums,k);
    }

    private void combine(List<List<Integer>> res,List<Integer> cur,int start,int[] nums,int k){
        if(cur.size() == k){
            res.add(new ArrayList<>(cur));
            return;
        }

        for (int i = start; i <nums.length ; i++) {
            cur.add(nums[i]);
            combine(res,cur,i+1,nums,k);
            cur.remove(cur.size()-1);
        }
    }

Golang代码实现

func subsets(nums []int) [][]int {
    res := make([][]int,0)
    for i:=0;i<=len(nums);i++{
        combine(nums,i,&res)
    }
    return res
}

func combine(nums []int,n int,res *[][]int){
    combineBackTrace(nums,0,n,[]int{},res)
}

func combineBackTrace(nums []int,cur int,n int,curNums []int,res *[][]int){
    if n == len(curNums){
        copyNum := make([]int,len(curNums))
        copy(copyNum,curNums)
        *res = append(*res,copyNum)
        return
    }

    for i:=cur;i<len(nums);i++{
        curNums = append(curNums,nums[i])
        combineBackTrace(nums,i+1,n,curNums,res)
        curNums = curNums[0:len(curNums)-1]
    }
}