LeetCode 78、子集

一、题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

二、题目解析

一般来说，回溯算法的思考步骤如下：

1、画出递归树，找到状态变量(回溯函数的参数)

2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件

3、确定选择列表，即需要把什么数据存储到结果里面

4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过

5、做出选择，递归调用该函数，进入下一层继续搜索

6、撤销选择，回到上一层的状态

翻译成代码为如下的形式，也就是回溯算法解题的一个模板：

// 1、画出递归树，找到状态变量(回溯函数的参数)
private void backtrack("原始参数") {
  
    // 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
    if ("终止条件") {
        // 一些逻辑操作（可有可无，视情况而定）
       // 比如，在 N 皇后问题中，在这一步把数据加入到了结果里面
       添加操作
        return;
    }
  
   // 3、确定选择列表，即需要把什么数据存储到结果里面
   // for 循环就是一个选择的过程
    for ("遍历本层集合中元素") {
      
        // 一些逻辑操作（可有可无，视情况而定）
       // 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
    
        // 5、做出选择，递归调用该函数，进入下一层继续搜索
        // 递归
        backtrack("新的参数");
      
        // 一些逻辑操作（可有可无，视情况而定）

        // 6、撤销选择，回到上一层的状态
    }
}

那么对于子集这道问题来说，我们按照模板进行一个思考：

1、画出递归树，找到状态变量(回溯函数的参数)

结合最终结果来画递归树。

2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件。

当访问的数组下标超过了 nums 数组的长度时，递归结束。

3、确定选择列表，即需要把什么数据存储到结果里面。

把本次递归访问的元素加入到 subset 数组中

4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过

由于题目要求我们去存储所有的子集，也就意味着不存在丢弃的操作，也就不需要剪枝了。

5、做出选择，递归调用该函数，进入下一层继续搜索

三、参考代码

Java

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
    public List<List<Integer>> subsets(int[] nums) {

        // 结果集合
        List<List<Integer>> sets = new ArrayList<List<Integer>>();

        // 每次的子集
        List<Integer> subset = new ArrayList<Integer>();

        // 执行回溯算法
        backtrack( 0 , nums , subset , sets);

        // 返回结果
        return sets;

    }

    // i 表示递归时正在访问的数组元素下标
    // nums 表示当前集合中的元素
    // subset 表示每次递归后生成的子集，就是路径上的那些元素
    // sets 表示最终生成的所有子集合
    private void backtrack( int i , int[] nums , List<Integer> subset , List<List<Integer>> sets ){

        // 每次确定好一个子集，都把它加入到结果集合中
        sets.add(new ArrayList<Integer>(subset));

        // 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
        // 本题中可以不加这个判断，大家可以思考一下为什么可以不加，结合 for 循环的边界来思考
        if( i >= nums.length){
            return;
        }

        for( int j = i ; j < nums.length ; j++ ){

            // 把本次递归访问的元素加入到 subset 数组中
            subset.add(nums[j]);

            // 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
            // 本题不需要剪枝

            // 5、做出选择，递归调用该函数，进入下一层继续搜索
            // 递归
            backtrack( j + 1 , nums , subset , sets);

            // 6、撤销选择，回到上一层的状态
            // 取消对 nums[i] 的选择
            subset.remove(subset.size() - 1);

        }

    }
}

Python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        """
        :param nums: List[int]
        :return: List[List[int]]
        """
        # 结果集合
        sets = []

        # 每次的子集
        subset = []

        # 执行回溯算法
        self.backtrack(0, nums, subset, sets)

        # 返回结果
        return sets

    def backtrack(self, i, nums, subset, sets):
        """
        :param i: int
        :param nums: List[int]
        :param subset: List[int]
        :param sets: List[List[int]]
        """
        # 每次确定好一个子集，都把它加入到结果集合中
        sets.append(subset[:])

        # 2、寻找结束条件，由于回溯算法是借助递归实现，所以也就是去寻找递归终止条件
        # 本题中可以不加这个判断，大家可以思考一下为什么可以不加，结合 for 循环的边界来思考
        if i >= len(nums):
            return

        for j in range(i, len(nums)):
            # 把本次递归访问的元素加入到 subset 数组中
            subset.append(nums[j])

            # 4、判断是否需要剪枝，去判断此时存储的数据是否之前已经被存储过
            # 本题不需要剪枝

            # 5、做出选择，递归调用该函数，进入下一层继续搜索
            # 递归
            self.backtrack(j + 1, nums, subset, sets)

            # 6、撤销选择，回到上一层的状态
            # 取消对 nums[i] 的选择
            subset.pop()

C++

class Solution {
public:
    // 生成所有子集
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> sets; // 结果集合
        vector<int> subset;       // 每次的子集
        backtrack(0, nums, subset, sets); // 执行回溯算法
        return sets;
    }

private:
    // 回溯算法
    void backtrack(int i, vector<int>& nums, vector<int>& subset, vector<vector<int>>& sets) {
        // 将当前子集加入到结果集合中
        sets.push_back(subset);

        // 回溯终止条件（实际上可以省略）
        if (i >= nums.size()) return;

        for (int j = i; j < nums.size(); j++) {
            // 将当前元素加入到子集中
            subset.push_back(nums[j]);
            // 递归调用，进入下一层
            backtrack(j + 1, nums, subset, sets);
            // 撤销选择，回到上一层状态
            subset.pop_back();
        }
    }
};

C

#include <stdlib.h>
#include <string.h>

// 动态数组结构体，用于存储子集
typedef struct {
    int** data;     // 二维数组存储所有子集
    int* sizes;     // 每个子集的大小
    int size;       // 当前子集的数量
    int capacity;   // 最大容量
} Result;

// 初始化动态数组
Result* initResult(int capacity) {
    Result* res = (Result*)malloc(sizeof(Result));
    res->data = (int**)malloc(capacity * sizeof(int*));
    res->sizes = (int*)malloc(capacity * sizeof(int));
    res->size = 0;
    res->capacity = capacity;
    return res;
}

// 动态数组扩容
void expandResult(Result* res) {
    res->capacity *= 2;
    res->data = (int**)realloc(res->data, res->capacity * sizeof(int*));
    res->sizes = (int*)realloc(res->sizes, res->capacity * sizeof(int));
}

// 将子集添加到结果集中
void addSubset(Result* res, int* subset, int subsetSize) {
    if (res->size == res->capacity) {
        expandResult(res);
    }
    res->data[res->size] = (int*)malloc(subsetSize * sizeof(int));
    memcpy(res->data[res->size], subset, subsetSize * sizeof(int));
    res->sizes[res->size] = subsetSize;
    res->size++;
}

// 回溯函数
void backtrack(int i, int* nums, int numsSize, int* subset, int subsetSize, Result* res) {
    // 将当前子集加入结果集
    addSubset(res, subset, subsetSize);

    for (int j = i; j < numsSize; j++) {
        // 添加当前元素
        subset[subsetSize] = nums[j];
        // 递归调用
        backtrack(j + 1, nums, numsSize, subset, subsetSize + 1, res);
    }
}

// 主函数接口
Result* subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    Result* res = initResult(1);
    int* subset = (int*)malloc(numsSize * sizeof(int));
    backtrack(0, nums, numsSize, subset, 0, res);
    free(subset);

    *returnSize = res->size;
    *returnColumnSizes = res->sizes;
    return res->data;
}

Node JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const sets = []; // 结果集合
    const subset = []; // 当前子集

    // 回溯函数
    const backtrack = (i) => {
        // 将当前子集加入结果集
        sets.push([...subset]);

        for (let j = i; j < nums.length; j++) {
            // 添加当前元素
            subset.push(nums[j]);
            // 递归调用
            backtrack(j + 1);
            // 撤销选择
            subset.pop();
        }
    };

    // 开始回溯
    backtrack(0);
    return sets;
};

Go

// 回溯函数
func backtrack(i int, nums []int, subset []int, sets *[][]int) {
    // 将当前子集加入结果集
    temp := make([]int, len(subset))
    copy(temp, subset)
    *sets = append(*sets, temp)

    for j := i; j < len(nums); j++ {
        // 添加当前元素
        subset = append(subset, nums[j])
        // 递归调用
        backtrack(j+1, nums, subset, sets)
        // 撤销选择
        subset = subset[:len(subset)-1]
    }
}

// 主函数接口
func subsets(nums []int) [][]int {
    var sets [][]int // 结果集合
    var subset []int // 当前子集
    backtrack(0, nums, subset, &sets)
    return sets
}