算法题/排列组合：不含重复数字的子集

题目

给定一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集。解集不能包含重复的子集。可以按任意顺序返回解集。

示例1：

输入：nums=[1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例2：

输入：nums=[0]
输出：[[],[0]]

解答

Java

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> subsets = new ArrayList<>();
    List<Integer> tempSubset = new ArrayList<>();
    for (int size = 0; size <= nums.length; size++) {
        backtracking(0, tempSubset, subsets, size, nums); // 不同的子集大小
    }
    return subsets;
}
private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets, final int size, final int[] nums) {
    if (tempSubset.size() == size) {
        subsets.add(new ArrayList<>(tempSubset));
        return;
    }
    for (int i = start; i < nums.length; i++) {
        tempSubset.add(nums[i]);
        backtracking(i + 1, tempSubset, subsets, size, nums);
        tempSubset.remove(tempSubset.size() - 1);
    }
}

JavaScript

function subsets(nums) {
    const subsets = [];
    const tempSubset = [];
    for (let size = 0; size <= nums.length; size++) {
        backtracking(0, tempSubset, subsets, size, nums); // 不同的子集大小
    }
    return subsets;
}

function backtracking(start, tempSubset, subsets, size, nums) {
    if (tempSubset.length === size) {
        subsets.push([...tempSubset]);
        return;
    }
    for (let i = start; i < nums.length; i++) {
        tempSubset.push(nums[i]);
        backtracking(i + 1, tempSubset, subsets, size, nums);
        tempSubset.pop();
    }
}

Python

def subsets(nums):
    subsets = []
    tempSubset = []
    for size in range(len(nums) + 1):
        backtracking(0, tempSubset, subsets, size, nums)  # 不同的子集大小
    return subsets

def backtracking(start, tempSubset, subsets, size, nums):
    if len(tempSubset) == size:
        subsets.append(tempSubset[:])
        return
    for i in range(start, len(nums)):
        tempSubset.append(nums[i])
        backtracking(i + 1, tempSubset, subsets, size, nums)
        tempSubset.pop()

Go

package main

import "fmt"

func subsets(nums []int) [][]int {
	subsets := [][]int{}
	tempSubset := []int{}
	for size := 0; size <= len(nums); size++ {
		backtracking(0, tempSubset, &subsets, size, nums) // 不同的子集大小
	}
	return subsets
}

func backtracking(start int, tempSubset []int, subsets *[][]int, size int, nums []int) {
	if len(tempSubset) == size {
		newSubset := make([]int, len(tempSubset))
		copy(newSubset, tempSubset)
		*subsets = append(*subsets, newSubset)
		return
	}
	for i := start; i < len(nums); i++ {
		tempSubset = append(tempSubset, nums[i])
		backtracking(i+1, tempSubset, subsets, size, nums)
		tempSubset = tempSubset[:len(tempSubset)-1]
	}
}

func main() {
	nums := []int{1, 2, 3}
	result := subsets(nums)
	fmt.Println(result)
}