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.

題目翻譯

給一個整數的陣列 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

/**
 * @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>>
    ) {
        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
{

    /**
     * @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

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)):
            # 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

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