Thinking process

Recursion => Draw a tree

• analyze the parameters needed in the helper function

Mistakes

• the ending condition should be larger than the length
  • or the last subset is not added
  • run the test with cautiously

API Method

ArrayList

remove(int index)

remove(Object object)

for this question, use the first one since integer is not object

Time Complexity

O (n*2^n)

T(n) = T(n - 1) + T(n - 2) + ... + T(0) + 1= O(2 ^ n)

http://www.1point3acres.com/bbs/thread-117602-1-1.html

http://www.jiuzhang.com/qa/1237/

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;

        dfsHelper(res, nums, new ArrayList<Integer>(), 0);

        return res;
    }

    private void dfsHelper(List<List<Integer>> res, int[] nums, List<Integer> list, int index) {
        if (index > nums.length) return;

        res.add(new ArrayList<>(list));

        for (int i = index; i < nums.length; ++i) {
            list.add(nums[i]);
            dfsHelper(res, nums, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}