90. Subsets II

/**
 * 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>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        if (nums == null) {
            return result;
        }
        if (nums.length == 0) {
            result.add(new ArrayList<Integer>());
            return result;
        }

        // Since the array can have duplicate numbers, thus we sort the array to bring
        // all duplicates together.
        Arrays.sort(nums);

        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++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            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>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        if (nums == null) {
            return result;
        }
        result.add(new ArrayList<Integer>());
        if (nums.length == 0) {
            return result;
        }

        // Since the array can have duplicate numbers, thus we sort the array to bring
        // all duplicates together.
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            int count = 1;
            while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                count++;
                i++;
            }
            int listSize = result.size();
            for (int j = 0; j < listSize; j++) {
                List<Integer> tempList = new ArrayList<Integer>(result.get(j));
                for (int k = 0; k < count; k++) {
                    tempList.add(nums[i]);
                    result.add(new ArrayList<Integer>(tempList));
                }
            }
        }

        return result;
    }
}