Problem
Given an array of unique integers, return all possible subsets (the power set).
Example
Input: [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]Solution
Backtracking. At each index, choose to include or exclude the element.
def subsets(nums):
result = []
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resultfunction subsets(nums) {
const result = [];
function backtrack(start, path) {
result.push([...path]);
for (let i = start; i < nums.length; i++) {
path.push(nums[i]);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(0, []);
return result;
}void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {
result.push_back(path);
for (int i = start; i < nums.size(); i++) {
path.push_back(nums[i]);
backtrack(nums, i + 1, path, result);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> path;
backtrack(nums, 0, path, result);
return result;
}public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
result.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, result);
path.remove(path.size() - 1);
}
}Complexity
- Time: O(2ⁿ)
- Space: O(n)
Explanation
Adding the current path at every recursion call captures every subset. Iterating from start (not 0) avoids duplicates.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?