个人记录-LeetCode 78. Subsets

问题：
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],
  []
]

这个问题基本上就是LeetCode 77. Combinations的变种，
其实就是给定1个数组，然后求出从中取出0个、1个、2个…….n个数组成的所有排列。

代码示例：

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();

        if (nums == null || nums.length < 1) {
            return rst;
        }

        rst.add(new ArrayList<>());

        List<List<Integer>> temp;
        for (int i = 1; i <= nums.length; ++i) {
            temp = combine(nums, i);
            rst.addAll(temp);
        }

        return rst;
    }

    //以下基本是LeetCode 77的代码，略微改了下接口
    private List<List<Integer>> combine(int[] nInts, int k) {
        List<List<Integer>> rst = new ArrayList<>();

        List<Integer> curr = new ArrayList<>();
        for (int i = 0; i <= nInts.length-k; ++i) {
            combineInner(rst, nInts, i, curr, k);
        }

        return rst;
    }

    private void combineInner(List<List<Integer>> rst, int[] nInts, int next, List<Integer> curr, int sz) {
        List<Integer> newList = new ArrayList<>(curr);
        newList.add(nInts[next]);

        if (newList.size() == sz) {
            rst.add(newList);
            return;
        }

        for (int i = next+1; i <= nInts.length - (sz - newList.size()); ++i) {
            combineInner(rst, nInts, i, newList, sz);
        }
    }
}

个人觉得这个问题，在分析完LeetCode 77后，10分容易想到答案。
但如果没有见过LeetCode 77，直接来解的话，对拆分问题的能力还是有较高要求的。