# LeetCode Solution, Medium, 78. Subsets

# [78. Subsets](https://leetcode.com/problems/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**.

#### 題目翻譯

給一個整數的陣列 `nums`，其中的元素都是唯一的。要列出這些元素所有可能的子集合，並且不限定排序。

### 解法解析

這個題目，官方有給了三種方式來解題。其中最好的是 Backtracking 的解法，所以範例會以 Backtrack 為主。其他解法會在 Python 中。因為題目是要找出所有的組合，所以用 Backtrack 的方式去遞迴找出所有的組合。

#### 程式範例

##### Go

```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

```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

```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

```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

```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**

```python
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)**

```python
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
            bitmask = bin(i)[3:]

            # append subset corresponding to that bitmask
            output.append([nums[j] for j in range(n) if bitmask[j] == '1'])

        return output
```

##### Rust

```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

```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
    }
}
```