Subsets - LeetCode Solution in Java

1. Introduction

The "Subsets" problem focuses on generating all possible subsets (the power set) from a given set of unique integers. It's a classic problem that explores the concept of backtracking and recursion in computer science.

2. Problem

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

3. Solution Steps

1. Use backtracking to explore all subsets.

2. Start with an empty list to hold the current subset.

3. Add the current subset to the result at each stage of recursion.

4. Iterate through the numbers, adding each number to the current subset and recursively continuing.

5. Backtrack by removing the last added number to explore other possibilities.

4. Solution in Java

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, 0);
    return result;
}

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

This solution employs a backtracking approach, starting from an empty subset and systematically adding elements to build up all possible subsets, backtracking as necessary to explore all combinations.

Explanation:

1. The backtrack method is utilized to generate subsets.

2. Each subset is added to the result list, starting with the empty subset.

3. The method iterates through nums, adding each element to tempList to form a new subset.

4. It then recursively calls itself with the next starting index (i + 1) to consider further elements.

5. After exploring each path, it backtracks by removing the last element added to tempList.

6. This process repeats, building up all possible subsets from the given numbers.