# 78. Subsets

### 題目敘述

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.

### 解法解析

#### 程式範例

##### 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
``````/**
* @param {number[]} nums
* @return {number[][]}
*/
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>>
) {
for (i in first until nums.size) {
backtrack(nums, i + 1, current, result)
current.remove(current[current.size - 1])
}
}
}
``````
##### PHP
``````class Solution
{

/**
* @param Integer[] \$nums
* @return Integer[][]
*/
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
``````

``````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)):
# generate bitmask, from 0..00 to 1..11

# append subset corresponding to that bitmask
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
}
}
``````