题解

题面描述

给定一个整数数组 $nums$，数组中的元素互不相同，要求返回该数组所有可能的子集（即幂集），但解集中不能包含重复的子集。
注意样例中只输出了非空子集，因此本题输出时不包含空集。
输出顺序按照递归生成时的顺序即可。

思路

我们可以采用 回溯法 来枚举所有可能的子集。
具体步骤如下：

• 定义一个递归函数，利用索引 $i$ 从数组 $nums$ 中依次选择元素。
• 在递归过程中，每当选择一个元素后，将当前构造的子集加入结果集合（若非空）。
• 然后从当前位置的下一个元素继续进行选择，直到遍历完整个数组。
• 回溯时撤销上一次的选择，继续选择其他可能的元素。

由于数组中没有重复的元素，所以每次选择都不会产生重复的子集。
时间复杂度为 $O(2^n)$，空间复杂度为 $O(n)$（递归深度）。

代码分析

1. 递归回溯框架
   使用一个递归函数 $backtrack(index)$，其中 $index$ 表示当前处理的起始位置。每一次递归都将当前已经选择的子集存入答案数组中（如果非空）。

2. 剪枝与状态恢复
   每次递归时，将下一个可能的元素加入当前子集，然后递归求解。递归返回后，回溯撤销选择。

3. ACM模式输入输出
   由于采用 ACM 模式，所以在 $main()$ 中需要读入所有输入（可能没有给出数组长度），然后输出每个子集，每个子集一行，元素之间以空格分隔。

C++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    // 用于存储所有非空子集
    vector<vector<int>> res;
    
    // 回溯函数，参数为当前数组、当前索引和当前子集
    void backtrack(vector<int>& nums, int index, vector<int>& curr) {
        // 如果当前子集非空，则保存到结果中
        if (!curr.empty()) {
            res.push_back(curr);
        }
        // 从当前索引开始，依次选择后面的每个数
        for (int i = index; i < nums.size(); i++) {
            // 选择当前数
            curr.push_back(nums[i]);
            // 递归继续选择下一个数
            backtrack(nums, i + 1, curr);
            // 撤销选择，进行回溯
            curr.pop_back();
        }
    }
    
    // 主函数，调用回溯函数获得所有子集
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> curr;
        backtrack(nums, 0, curr);
        return res;
    }
};

int main(){
    vector<int> nums;
    int x;
    // 读入所有整数，直到结束
    while(cin >> x){
        nums.push_back(x);
    }
    
    Solution sol;
    vector<vector<int>> ans = sol.subsets(nums);
    
    // 输出每个子集，每个子集一行，数字之间以空格分隔
    for(auto &subset : ans){
        for(int i = 0; i < subset.size(); i++){
            cout << subset[i];
            if(i != subset.size()-1) cout << " ";
        }
        cout << "\n";
    }
    return 0;
}

Python

# 定义 Solution 类，实现求子集的功能
class Solution:
    def subsets(self, nums):
        # 结果列表，用于存储所有非空子集
        res = []
        # 辅助递归函数，参数 curr 为当前构造的子集，index 为当前处理的起始位置
        def backtrack(index, curr):
            # 如果当前子集非空，则加入结果
            if curr:
                res.append(curr[:])
            # 从 index 开始，遍历后续每个元素
            for i in range(index, len(nums)):
                # 选择当前数字
                curr.append(nums[i])
                # 递归调用，继续构造子集
                backtrack(i + 1, curr)
                # 撤销选择，回溯
                curr.pop()
        backtrack(0, [])
        return res

if __name__ == '__main__':
    import sys
    # 从标准输入读取所有数字
    nums = list(map(int, sys.stdin.read().strip().split()))
    sol = Solution()
    ans = sol.subsets(nums)
    # 输出每个子集，每个子集一行，数字之间用空格分隔
    for subset in ans:
        print(" ".join(map(str, subset)))

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    // 定义 Solution 类，包含求子集的函数
    static class Solution {
        // 用于存储所有非空子集
        List<List<Integer>> res = new ArrayList<>();

        // 回溯函数，参数 curr 表示当前子集，index 表示从哪个位置开始选择
        public void backtrack(int[] nums, int index, List<Integer> curr) {
            // 如果当前子集非空，则保存到结果列表
            if (!curr.isEmpty()) {
                res.add(new ArrayList<>(curr));
            }
            // 从 index 开始，遍历每个可能的元素
            for (int i = index; i < nums.length; i++) {
                // 选择当前元素
                curr.add(nums[i]);
                // 递归继续选择下一个元素
                backtrack(nums, i + 1, curr);
                // 回溯，撤销选择
                curr.remove(curr.size() - 1);
            }
        }

        // 主函数，调用回溯函数得到所有子集
        public List<List<Integer>> subsets(int[] nums) {
            backtrack(nums, 0, new ArrayList<>());
            return res;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取输入数字，存入数组
        List<Integer> numsList = new ArrayList<>();
        while(sc.hasNextInt()){
            numsList.add(sc.nextInt());
        }
        int n = numsList.size();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = numsList.get(i);
        }
        
        Solution sol = new Solution();
        List<List<Integer>> ans = sol.subsets(nums);
        // 输出每个子集，每个子集一行，数字之间用空格分隔
        for(List<Integer> subset : ans){
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < subset.size(); i++){
                sb.append(subset.get(i));
                if(i != subset.size() - 1) sb.append(" ");
            }
            System.out.println(sb.toString());
        }
    }
}

Leetcode 56.子集-原题链接

题目内容

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

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

输入描述

输出描述

样例1

输入

1 2 3

输出

1
1 2
1 2 3
1 3 
2
2 3
3

提示

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