Subsets - Generating All Combinations with Backtracking (Java)

Introduction:
Hello everyone! Today, we're diving into a fundamental problem that's perfect for understanding recursive combinatorial generation: "Subsets" (LeetCode #78).
Given an array of unique integers, our goal is to return all possible subsets (the power set). This is a classic application of the backtracking algorithm using the "pick or don't pick" strategy.
Understanding the Problem:
You are given an integer array nums
containing unique integers. Your task is to return a list of all possible subsets of nums
. The solution set must not contain duplicate subsets, and you can return them in any order.
What is a subset? A subset is a set formed by taking some or none or all of the elements from another set. For example, if nums = [1,2]
, its subsets are []
, [1]
, [2]
, [1,2]
.
Examples:
Input:
nums = [1, 2, 3]
- Output:
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
- Output:
Input:
nums = [7]
- Output:
[[], [7]]
- Output:
My Thought Process & Approach (Backtracking / "Pick or Don't Pick"):
The problem asks for "all possible subsets," which is a strong indicator of a combinatorial generation algorithm, typically solved with backtracking (or recursion with state management).
The core idea for "Subsets" is very intuitive: for each element in the input array nums
, we have two fundamental choices:
Include the current element in the subset we are currently building.
Exclude the current element from the subset we are currently building.
We explore both paths recursively.
The Algorithm Steps (helper
function):
Let's define our recursive helper function with parameters that capture our current state:
A
: The inputnums
array.curr
: AnArrayList<Integer>
representing the subset we are currently building.idx
: The index of the current element inA
that we are considering whether to include or exclude.ans
: TheList<List<Integer>>
where we will store all the final subsets.
Base Case (Termination Condition):
When
idx == A.length
, it means we have processed all elements in thenums
array. At this point, thecurr
list represents a complete subset.We add a copy of
curr
to ourans
list. It's crucial to add anew ArrayList<>(curr)
becausecurr
is a reference and will be modified later as we backtrack. Adding a copy ensures we store the current state of the subset.Then, we
return
to the previous recursive call.
Recursive Steps (Making Choices and Backtracking):
Choice 1: Include
A[idx]
Add
A[idx]
to ourcurr
subset.Make a recursive call to
helper(A, curr, idx + 1, ans)
to process the next element in the array.
Backtrack (Crucial Step): After the recursive call for "including
A[idx]
" returns, we must removeA[idx]
fromcurr
(curr.remove(curr.size() - 1)
). This is the "backtrack" step. It resets thecurr
list to its state beforeA[idx]
was added, allowing us to correctly explore the "exclude" path for the sameidx
.Choice 2: Exclude
A[idx]
Since we've already "backtracked" by removing
A[idx]
, thecurr
list is now in the state whereA[idx]
is not included.Make a recursive call to
helper(A, curr, idx + 1, ans)
to process the next element, effectively exploring the path whereA[idx]
was skipped.
This "pick or don't pick" approach, combined with backtracking, systematically explores every single combination of elements, guaranteeing that all 2^N
subsets are generated exactly once.
Java Code Implementation:
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<Integer> curr = new ArrayList<Integer>();
int idx = 0;
List<List<Integer>> ans = new ArrayList<List<Integer>>();
helper(nums,curr,idx,ans);
return ans;
}
public void helper(int[] A, List<Integer> curr, int idx, List<List<Integer>> ans){
if(idx==A.length){
ans.add(new ArrayList<>(curr));
return;
}
curr.add(A[idx]);
helper(A,curr,idx+1,ans);
curr.remove(curr.size()-1);
helper(A,curr,idx+1,ans);
}
}
Time and Space Complexity Analysis:
Time Complexity: O( 2^N)
For an array of size
N
, there are exactly2^N
possible subsets (each element can either be in a subset or not).Our backtracking algorithm explores each of these
2^N
possibilities.
Space Complexity: O(N) (Auxiliary Space)
When analyzing space complexity for recursive algorithms, we typically consider the auxiliary space used by the algorithm during its execution, not counting the space for the final output.
The primary consumer of auxiliary space here is the recursion call stack. The maximum depth of the recursion will be
N
(when we process each element from index 0 toN-1
).
Subscribe to my newsletter
Read articles from Kaushal Maurya directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
