Leetcode78——Subsets

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. 问题描述

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

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

2. 求解

递归法

这道题类似于数组的组合问题，可以用递归法求解。N个数中每个数都分为要与不要两种情况，求解的过程如下图。递归的边界条件为N个数都遍历完了。

public class Solution {
    public static List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<List<Integer>> subsets(int[] nums) {
        result.clear();
        result.add(new ArrayList<Integer>());
        combination(nums, 0, new ArrayList<Integer>());
        return result;
    }
    
    public void combination(int[] nums, int index, List<Integer> list) {
        if(index == nums.length) {
            return;
        }
        combination(nums, index + 1, new ArrayList<Integer>(list));
        list.add(nums[index]);
        result.add(list);
        combination(nums, index + 1, new ArrayList<Integer>(list));
    }
}