題目敘述
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
nums are unique.
題目翻譯
給一個整數的陣列 nums，其中的元素都是唯一的。要列出這些元素所有可能的子集合，並且不限定排序。
解法解析
這個題目，官方有給了三種方式來解題。其中最好的是 Backtracking 的解法，所以範例會以 Backtrack 為主。其他解法會在 Python 中。因為題目是要找出所有的組合，所以用 Backtrack 的方式去遞迴找出所有的組合。
程式範例
Go
func subsets(nums []int) [][]int {
output := [][]int{}
var backtrack func(int, []int)
backtrack = func(first int, curr []int) {
output = append(output, append([]int{}, curr...))
for i := first; i < len(nums); i++ {
backtrack(i+1, append(curr, nums[i]))
}
}
backtrack(0, []int{})
return output
}
JavaScript
var subsets = function (nums) {
const backtrack = (first = 0, curr = []) => {
output.push(curr);
for (let i = first; i < nums.length; i++) {
backtrack(i + 1, [...curr, nums[i]]);
}
};
const output = [];
backtrack();
return output;
};
Kotlin
class Solution {
fun subsets(nums: IntArray): List<List<Int>> {
val output = ArrayList<ArrayList<Int>>()
backtrack(nums, 0, ArrayList<Int>(), output)
return output
}
private fun backtrack(
nums: IntArray,
first: Int,
current: ArrayList<Int>,
result: ArrayList<ArrayList<Int>>
) {
result.add(ArrayList(current))
for (i in first until nums.size) {
current.add(nums[i])
backtrack(nums, i + 1, current, result)
current.remove(current[current.size - 1])
}
}
}
PHP
class Solution
{
function subsets($nums)
{
$this->output = array();
$this->backtrack($nums, 0, array());
return $this->output;
}
function backtrack($nums, $first, $curr)
{
array_push($this->output, $curr);
for ($i = $first; $i < count($nums); $i++) {
$num = $nums[$i];
if (!in_array($num, $curr)) {
array_push($curr, $num);
$this->backtrack($nums, $i, $curr);
array_pop($curr);
}
}
}
}
Python
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(first=0, curr=[]):
output.append(curr[:])
for i in range(first, len(nums)):
backtrack(i+1, curr + [nums[i]])
output = []
backtrack()
return output
Cascading
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
subset = [[]]
for num in nums:
subset += [item+[num] for item in subset]
return subset
Lexicographic (Binary Sorted)
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
output = []
for i in range(2**n, 2**(n + 1)):
bitmask = bin(i)[3:]
output.append([nums[j] for j in range(n) if bitmask[j] == '1'])
return output
Rust
impl Solution {
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut output = Vec::new();
Self::backtrack(&nums, &mut output, 0, &mut Vec::new());
return output;
}
pub fn backtrack(nums: &Vec<i32>, res: &mut Vec<Vec<i32>>, first: i32, curr: &mut Vec<i32>) {
for i in first..nums.len() as i32 {
curr.push(nums[i as usize].clone());
Self::backtrack(nums, res, i+1, curr);
curr.pop();
}
res.push(curr.clone());
}
}
Swift
class Solution {
func subsets(_ nums: [Int]) -> [[Int]] {
func backtrack(_ first: Int, _ curr: [Int]) {
output.append(curr)
for i in first..<nums.count {
var newCurr = curr
newCurr.append(nums[i])
backtrack(i+1, newCurr)
}
}
var output: [[Int]] = []
backtrack(0, [])
return output
}
}