leetcode78：子集

题目链接

leetcode

题目描述

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

C++ 代码

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

/*
    回溯法，深度优先搜索
    
    一共枚举 n 层，start 表示当前数字从 nums[start] 开始选，保证数字递增。

    时间复杂度：O((2^n)*n)
        一共枚举 2^n 个数，每个数枚举 n 位。
        所以，总时间复杂度是 O((2^n)*n)
    空间复杂度：O(n)
        递归使用的栈空间。
        在最坏的情况下，递归的深度可以达到 n，因此空间复杂度为 O(n)。
*/
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        if (nums.empty()) return {};
        dfs(nums, 0);
        return res;
    }
    
    void dfs(vector<int>& nums, int start) {
        res.push_back(path);

        for (int i = start; i < nums.size(); i ++) {
            // 做选择
            path.push_back(nums[i]);
            // 通过 start 参数控制树枝的遍历，避免产生重复的子集
            dfs(nums, i + 1);
            // 撤销选择
            path.pop_back();
        }
    }

private:
    vector<vector<int>> res;
    vector<int> path;
};

/*
    思路同上
*/
class Solution_1 {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        if (nums.empty()) return {};
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int>& nums, int start) {
        if (start == nums.size()) {
            res.push_back(path);
            return;
        }

        // 选择
        path.push_back(nums[start]);
        dfs(nums, start + 1);
        // 撤销选择
        path.pop_back();
        dfs(nums, start + 1);
    }

private:
    vector<vector<int>> res;
    vector<int> path;
};

/*
    集合的二进制表示

    假设集合大小是 n，枚举 0, 1, 2, ..., 2^n-1 ，一共 2^n 个数。
    每个数表示一个子集，
        若该数字的二进制表示的第 i 位是 1，则该子集包含第 i 个数；
        否则，则不包含第 i 个数。

    时间复杂度：O((2^n)*n)
        一共枚举 2^n 个数，每个数枚举 n 位。
        所以，总时间复杂度是 O((2^n)*n)。
*/
class Solution_2 {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        if (nums.empty()) return {};
        
        int n = nums.size();
        for (int i = 0; i < 1 << n; i ++) {
            for (int j = 0; j < n; j ++) {
                if (i >> j & 1) {
                    path.push_back(nums[j]);
                }
            }
            res.push_back(path);
            path.clear();
        }

        return res;
    }

private:
    vector<vector<int>> res;
    vector<int> path;
};

int main() {
    Solution solution;
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> subsets = solution.subsets(nums);
    cout << "Subsets of ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << "are:" << endl;
    for (const vector<int>& subset : subsets) {
        for (int num : subset) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"sort"
)

// 比较两个子集集合是否相同（元素顺序无关）
func compareSubsets(a, b [][]int) bool {
	if len(a) != len(b) {
		return false
	}

	// 生成标准化字符串标识
	createKey := func(s []int) string {
		sorted := make([]int, len(s))
		copy(sorted, s)
		sort.Ints(sorted)
		return fmt.Sprintf("%v", sorted)
	}

	// 统计出现次数
	counter := make(map[string]int)
	for _, s := range a {
		counter[createKey(s)]++
	}

	// 验证所有元素
	for _, s := range b {
		key := createKey(s)
		if counter[key] <= 0 {
			return false
		}
		counter[key]--
	}
	return true
}

/*
    回溯算法：
        使用回溯算法生成所有可能的子集。
        回溯算法通过递归模拟所有可能的选择路径，每次选择一个数字加入当前路径，并在递归返回时恢复状态。
    路径和选择列表：
        路径：当前生成的部分子集。
        选择列表：剩余可选择的数字。
        每次从选择列表中选择一个数字加入路径，并从选择列表中移除该数字。
    结束条件：
        每次进入 backtrack 时，当前路径 path 都是一个有效的子集，将其加入结果列表。
    状态恢复：
        在递归返回时，恢复路径的状态，以便尝试其他选择。

    时间复杂度：O(n*2^n)
        生成所有子集的时间复杂度为 O(2^n)，其中 n 是输入数组的长度。
        每个子集的生成时间复杂度为 O(n)，因为需要将路径复制到结果列表中。
        因此，总时间复杂度为 O(n*2^n)。
    空间复杂度：
        递归调用栈的深度为 O(n)。
        路径 path 的空间复杂度为 O(n)。
        结果列表 result 的空间复杂度为 O(2^n)，因为需要存储所有子集。
        因此，总空间复杂度为 O(n*2^n)。
*/
func subsets(nums []int) [][]int {
    var result [][]int
    var path []int

    var dfs func(int)
    dfs = func(start int) {
        // 每次进入 dfs 时，当前路径都是一个有效的子集
        result = append(result, append([]int{}, path...))

        // 回溯算法标准框架
        for i := start; i < len(nums); i ++ {
            // 做选择
            path = append(path, nums[i])
            // 递归进入下一层
            dfs(i + 1)
            // 撤销选择
            path = path[:len(path)-1]
        }
    }

    dfs(0)
    return result
}

func main() {
	// 测试用例
	testCases := []struct {
		nums    []int
		expected [][]int
	}{
		{
			nums: []int{1, 2, 3},
			expected: [][]int{
				{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3},
			},
		},
		{
			nums: []int{0},
			expected: [][]int{
				{}, {0},
			},
		},
		{
			nums: []int{},
			expected: [][]int{
				{},
			},
		},
	}

	for i, tc := range testCases {
		fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
		result := subsets(tc.nums)

		if compareSubsets(result, tc.expected) {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
        }
	}
}