78. Subsets

/**
 * Backtracking (Recursion)
 *
 * T(n) = 0 × (n C 0) + 1 × (n C 1) + 2 × (n C 2) + … + n × (n C n)
 *
 * Note that (n C k) = (n C n-k). Therefore:
 *
 * T(n) = 0 × (n C n) + 1 × (n C n-1) + 2 × (n C n-2) + … + n × (n C 0)
 *
 * If we add these two together, we get
 *
 * 2T(n) = n × (n C 0) + n × (n C 1) + … + n × (n C n)
 *
 * = n × (n C 0 + n C 1 + … + n C n)
 *
 * As per binomial theorem, (n C 0 + n C 1 + … + n C n) = 2^n, so
 *
 * 2*T(n) = n * 2^n => T(n) = n * 2^(n-1) = O(n * 2^n)
 *
 * Time Complexity: O(N * 2 ^ N) Refer https://stackoverflow.com/a/20711498
 *
 * Space Complexity: O(N) (Excluding the result space)
 *
 * N = Length of input nums array
 */
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        if (nums == null) {
            return result;
        }
        if (nums.length == 0) {
            result.add(new ArrayList());
            return result;
        }

        backtrack(result, new ArrayList<Integer>(), nums, 0);

        return result;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
        list.add(new ArrayList<Integer>(tempList));
        for (int i = start; i < nums.length; i++) {
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

/**
 * Iterative Solution
 *
 * Time Complexity: O(N * 2 ^ N) Refer https://stackoverflow.com/a/20711498
 *
 * Space Complexity: O(1) (Excluding the result space)
 *
 * N = Length of input nums array
 */
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        if (nums == null) {
            return result;
        }
        result.add(new ArrayList<Integer>());
        if (nums.length == 0) {
            return result;
        }

        for (int num : nums) {
            int listSize = result.size();
            for (int j = 0; j < listSize; j++) {
                List<Integer> tempList = new ArrayList<Integer>(result.get(j));
                tempList.add(num);
                result.add(tempList);
            }
        }

        return result;
    }
}