LeetCode刷题笔记 回溯算法

78 子集 (opens new window)

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

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

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

解析：

class Solution {
public:
    void bt(vector<int>& nums, int start, vector<int>& track, vector<vector<int>>& ans){
        ans.push_back(track);
        for(int i=start;i<nums.size();++i){
            track.push_back(nums[i]);
            bt(nums,i+1,track,ans);
            track.pop_back();
        }
        return;
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> track;
        vector<vector<int>> ans;
        bt(nums,0,track,ans);
        return ans; 
    }
};

90 子集 II (opens new window)

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

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

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

解析：

class Solution {
public:
    void bt(vector<int>& nums, int start, vector<int>& track, vector<vector<int>>& ans, vector<bool>& visited){
        ans.push_back(track);
        for(int i=start;i<nums.size();++i){
            if(i>start&&nums[i]==nums[i-1]&&!visited[i-1]){
                continue;
            }
            track.push_back(nums[i]);
            visited[i] = true;
            bt(nums,i+1,track,ans,visited);
            visited[i] = false;
            track.pop_back();
        }
        return;
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> track;
        vector<vector<int>> ans;
        // 重复元素判断是否使用过，同一子集中可以重复使用，不同子集中不行，不然出现重复子集
        vector<bool> visited(nums.size(),false);
        // 去重要排序，不然不容易识别重复元素
        sort(nums.begin(),nums.end());
        bt(nums,0,track,ans,visited);
        return ans;
    }
};