Description:
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.
Examples:
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]]Solution in Python:
To solve the problem of generating all possible subsets (the power set) of a given list of unique integers in Python, we can use backtracking.
Approach:
- Initialize Variables:
- A list
resto store all the subsets. - A temporary list
subsetto store the current subset being constructed.
- A list
- Backtracking Function:
- This function will recursively build the subsets.
- Add the current subset (a copy of it) to the result list
res. - Iterate through the elements starting from the current index to the end of the list.
- Include the current element in the subset and recursively call the backtracking function with the next index.
- Remove the last element from the subset to backtrack and explore other possibilities.
- Base Case and Recursive Case:
- There is no specific base case since every subset, including the empty subset, is valid.
- The recursive case involves including the current element in the subset and exploring further.
Python
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(start: int, subset: List[int]):
# Add a copy of the current subset to the result
res.append(subset[:])
# Iterate over the range starting from 'start' to the end of the list
for i in range(start, len(nums)):
# Include nums[i] in the current subset
subset.append(nums[i])
# Recursively call backtrack with the next index
backtrack(i + 1, subset)
# Backtrack by removing the last element
subset.pop()
res = []
backtrack(0, [])
return resExplanation:
- Function
subsets:- This is the main function that initializes the result list
resand starts the backtracking process by callingbacktrackwith the initial parameters.
- This is the main function that initializes the result list
- Function
backtrack:- Parameters:
start: The current starting index for the subset.subset: The current subset being constructed.
- Add a copy of the current subset to the result list
res. - Iterate from
startto the end of the list. For each indexi:- Add
nums[i]to the current subsetsubset. - Call
backtrackrecursively withi + 1as the new start to continue building the subset. - After returning from the recursive call, remove
nums[i]fromsubsetto backtrack.
- Add
- Parameters:
- Backtracking Logic:
- This approach ensures that all possible subsets are generated by exploring all combinations of elements.
- The backtracking process allows for the exploration of all subsets by including and excluding each element in turn.
This implementation ensures that all subsets of the given list of unique integers are generated, and it is efficient for the given constraints (1 <= nums.length <= 10).
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
// Initialize the result array to store all subsets
let res = [];
// Backtracking helper function
function backtrack(start, subset) {
// Add a copy of the current subset to the result
res.push([...subset]);
// Iterate over the range from start to the end of the nums array
for (let i = start; i < nums.length; i++) {
// Add nums[i] into the current subset
subset.push(nums[i]);
// Use next integers to complete the subset
backtrack(i + 1, subset);
// Backtrack by removing the last element
subset.pop();
}
}
// Start the backtracking with index 0 and an empty subset
backtrack(0, []);
// Return the result containing all subsets
return res;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> subsets(int[] nums) {
// Initialize the result list to store all subsets
List<List<Integer>> res = new ArrayList<>();
// Start the backtracking process with the initial parameters
backtrack(0, nums, new ArrayList<>(), res);
return res;
}
private void backtrack(int start, int[] nums, List<Integer> subset, List<List<Integer>> res) {
// Add a copy of the current subset to the result
res.add(new ArrayList<>(subset));
// Iterate over the range from start to the end of the nums array
for (int i = start; i < nums.length; i++) {
// Add nums[i] into the current subset
subset.add(nums[i]);
// Use next integers to complete the subset
backtrack(i + 1, nums, subset, res);
// Backtrack by removing the last element
subset.remove(subset.size() - 1);
}
}
}Solution in C#:
C#
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> Subsets(int[] nums) {
// Initialize the result list to store all subsets
List<IList<int>> res = new List<IList<int>>();
// Start the backtracking process with the initial parameters
Backtrack(0, nums, new List<int>(), res);
return res;
}
private void Backtrack(int start, int[] nums, List<int> subset, List<IList<int>> res) {
// Add a copy of the current subset to the result
res.Add(new List<int>(subset));
// Iterate over the range from start to the end of the nums array
for (int i = start; i < nums.Length; i++) {
// Add nums[i] into the current subset
subset.Add(nums[i]);
// Use next integers to complete the subset
Backtrack(i + 1, nums, subset, res);
// Backtrack by removing the last element
subset.RemoveAt(subset.Count - 1);
}
}
}