Subsets I and II

78,90.Subsets I & II

Array

Backtracking

Recursion

Problem Statements:

I: Given an integer array nums of unique elements, return all possible subsets.
II: Given an integer array nums that may contain duplicates, return all possible subsets. The solution must not contain duplicate subsets.

Examples:

I: Input:

nums = [1,2,3]

Output:

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

II: Input:

nums = [1,2,2]

Output:

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

Java Solutions:

// Subsets I: All unique elements
class Solution {
    public ListInteger>> subsets(int[] nums) {
        ListInteger>> result = new ArrayList<>();
        backtrack(result, nums, 0, new ArrayList<>());
        return result;
    }

    public void backtrack(ListInteger>> result, 
            int[] nums, int index, List<Integer> tempList) {
        
        result.add(new ArrayList<>(tempList));  // Add every subset
                    
        for (int i = index; i < nums.length; i++) {
            tempList.add(nums[i]);
            backtrack(result, nums, i + 1, tempList);  // Move to next element
            tempList.remove(tempList.size() - 1);
        }
    }
}

// Subsets II: Handle duplicates
class Solution {
    public ListInteger>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);  // Sort to handle duplicates
        ListInteger>> result = new ArrayList<>();
        backtrack(result, nums, 0, new ArrayList<>());
        return result;
    }

    private void backtrack(ListInteger>> result, 
            int[] nums, int index, List<Integer> tempList) {
        
        result.add(new ArrayList<>(tempList));
        
        for (int i = index; i < nums.length; i++) {
            if (i > index && nums[i] == nums[i-1]) continue;  // Skip duplicates
            tempList.add(nums[i]);
            backtrack(result, nums, i + 1, tempList);
            tempList.remove(tempList.size() - 1);
        }
    }
}

Key Differences:

1. I: No need to handle duplicates
2. II: Must sort array first to handle duplicates
3. II: Skip adjacent duplicate numbers using i > index check
4. II: Same backtracking structure but with duplicate check

Complexity:

I: Time: O(2^n) | Space: O(n)
II: Time: O(2^n) | Space: O(n)