Problem Statement:
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.
Example 1:
Input: nums = [1,2,3]
Output:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output:[[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10- All the numbers of
numsare unique.
Approach:
- Start with an empty subset
(path). - At each step, add the
current subsetto the result. - Iterate from the current start index to the end of the array:
Include the elementin thesubset.- Recurse to build further subsets from the next index.
- Backtrack by removing the
last elementto explore other possibilities.
Continueuntil all combinations are generated.
Time Complexity:
Time Complexity = O(2n)
Space Complexity:
Space Complexity = O(2n)
Dry Run
Input: arr = [1, 2, 3]
Step 0: Start Function backtrackSubsets([1, 2, 3]) n = 3 result = [] path = [] Call backtrack([], 0) → Push [] → result = [[]] First loop: i = 0 → arr[0] = 1 path.push(1) → path = [1] Call backtrack([1], 1) → Push [1] → result = [[], [1]] Loop i = 1 → arr[1] = 2 path.push(2) → path = [1, 2] Call backtrack([1, 2], 2) → Push [1, 2] → result = [[], [1], [1, 2]] Loop i = 2 → arr[2] = 3 path.push(3) → path = [1, 2, 3] Call backtrack([1, 2, 3], 3) → Push [1, 2, 3] → result = [[], [1], [1, 2], [1, 2, 3]] Loop ends (start = 3 >= arr.length) path.pop() → path = [1, 2] Loop ends path.pop() → path = [1] Loop i = 2 → arr[2] = 3 path.push(3) → path = [1, 3] Call backtrack([1, 3], 3) → Push [1, 3] → result = [[], [1], [1, 2], [1, 2, 3], [1, 3]] Loop ends path.pop() → path = [1] Loop ends path.pop() → path = [] Loop i = 1 → arr[1] = 2 path.push(2) → path = [2] Call backtrack([2], 2) → Push [2] → result = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2]] Loop i = 2 → arr[2] = 3 path.push(3) → path = [2, 3] Call backtrack([2, 3], 3) → Push [2, 3] → result = [..., [2, 3]] Loop ends path.pop() → path = [2] Loop ends path.pop() → path = [] Loop i = 2 → arr[2] = 3 path.push(3) → path = [3] Call backtrack([3], 3) → Push [3] → result = [..., [3]] Loop ends path.pop() → path = [] Loop ends Step 3: End Return result = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Output:
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
var subsets = function(arr) {
let result = [];
let backtrack = (path, start) => {
result.push([...path]);
for(let i = start; i < arr.length; i++){
path.push(arr[i]);
backtrack(path, i+1);
path.pop();
}
}
backtrack([], 0);
return result;
};
def subsets(arr):
result = []
def backtrack(path, start):
result.append(list(path))
for i in range(start, len(arr)):
path.append(arr[i])
backtrack(path, i + 1)
path.pop()
backtrack([], 0)
return result
# Example
arr = [1, 2, 3]
print(subsets(arr))
import java.util.*;
public class Main {
static void backtrack(int[] arr, List path, int start, List> result) {
result.add(new ArrayList<>(path));
for (int i = start; i < arr.length; i++) {
path.add(arr[i]);
backtrack(arr, path, i + 1, result);
path.remove(path.size() - 1);
}
}
static List> subsets(int[] arr) {
List> result = new ArrayList<>();
backtrack(arr, new ArrayList<>(), 0, result);
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3};
List> res = subsets(arr);
for (List subset : res) {
System.out.println(subset);
}
}
}
void backtrack(vector& arr, vector& path, int start, vector>& result) {
result.push_back(path);
for (int i = start; i < arr.size(); i++) {
path.push_back(arr[i]);
backtrack(arr, path, i + 1, result);
path.pop_back();
}
}
vector> subsets(vector& arr) {
vector> result;
vector path;
backtrack(arr, path, 0, result);
return result;
}
int main() {
vector arr = {1, 2, 3};
vector> res = subsets(arr);
for (auto& subset : res) {
cout << "{ ";
for (int num : subset) cout << num << " ";
cout << "}" << endl;
}
}
void backtrack(int arr[], int n, int path[], int pathLen, int start) {
printf("{ ");
for (int i = 0; i < pathLen; i++) printf("%d ", path[i]);
printf("}\n");
for (int i = start; i < n; i++) {
path[pathLen] = arr[i];
backtrack(arr, n, path, pathLen + 1, i + 1);
}
}
int main() {
int arr[] = {1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int path[100];
backtrack(arr, n, path, 0, 0);
return 0;
}
using System;
using System.Collections.Generic;
class Program {
static void Backtrack(List arr, List path, int start, List> result) {
result.Add(new List(path));
for (int i = start; i < arr.Count; i++) {
path.Add(arr[i]);
Backtrack(arr, path, i + 1, result);
path.RemoveAt(path.Count - 1);
}
}
static List> Subsets(List arr) {
var result = new List>();
Backtrack(arr, new List(), 0, result);
return result;
}
static void Main() {
var arr = new List {1, 2, 3};
var res = Subsets(arr);
foreach (var subset in res) {
Console.Write("{ ");
foreach (var num in subset) Console.Write(num + " ");
Console.WriteLine("}");
}
}
}
