1 子集

分析

子集的组成可以看作与集合大小相同的二进制串的所有情况。

找到某个二进制数1的索引方法：mask < (1 << n)

Python
C++

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        for mask in range(1 << n):  # 最大的值即是1<<n
            iter = []
            for i in range(n):
                if mask & (1 << i): iter.append(nums[i])
            ans.append(iter)
        return ans

#include <vector>
class Solution {
public:
    vector<int> iter;
    vector<vector<int>> ans;
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();  // 最长的子集的长度就是集合元素的个数
        for (int mask = 0; mask < (1 << n); ++mask) {  // 在0-n-1之中遍历
            iter.clear();  // iter用于存储数对应的二进制
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    // 找到mask二进制1的位置
                    iter.push_back(nums[i]);
                }
            }
            ans.push_back(iter);
        }
        return ans;
    }
};

2 子集Ⅱ

分析

该题和上一题基本一致，但是要注意不包含重复的子集和原集合中元素可以重复，这就要求：

数组得先进行排序
在将集合放入结果列表中时需要判定数组是否就在其中

C++
Python

#include <vector>
#include <algorithm>
#include <set>

class Solution {
public:
    std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
        std::vector<std::vector<int>> ans;
        std::vector<int> iter;
        int n = nums.size();
        // 对 nums 排序，以便处理重复元素
        std::sort(nums.begin(), nums.end());
        // 使用 std::set 存储子集，自动去除重复
        std::set<std::vector<int>> subsets;
        // 使用位掩码生成所有子集
        for (int mask = 0; mask < (1 << n); ++mask) {
            iter.clear();
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    iter.push_back(nums[i]);
                }
            }
            subsets.insert(iter); // 自动去除重复
        }
        // 将 std::set 中的子集转换为结果
        for (const auto& subset : subsets) {
            ans.push_back(subset);
        }
        
        return ans;
    }
};

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        nums.sort()
        for mask in range(1 << n):
            iter = []
            for i in range(n):
                if mask & (1 << i): iter.append(nums[i])
            if iter not in ans:
                ans.append(iter)
        return ans

3 全排列

分析

回溯法：

迭代地将数放在不同的位置而产生不同的组合，若组合未出现在结果中就加入，否则，将最后一个元素弹出，在该位置迭代其他数。

C++
Python

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        dfs(nums, path, result);
        return result;       
    }

    void dfs (vector<int> nums, vector<int>& path, vector<vector<int>>& result) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        } 
        for (auto i : nums) {
            if (find(path.begin(), path.end(), i) == path.end()) {
                path.push_back(i);
                dfs(nums, path, result);
                path.pop_back();
            }
        }
    } 
};

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []
        def dfs(nums: List[int], path: List[int], result: List[List[int]]) -> None:
            if len(path) == len(nums):
                result.append(path[:])  # 防止浅拷贝的问题
                return
            for i in nums:
                if i not in path:
                    path.append(i)
                    dfs(nums, path, result)
                    path.pop()
        dfs(nums, path, result)
        return result