【lintcode】子集问题

梦里梦外; 2022-05-24 08:45 234阅读 0赞

这里的子集问题是指给定一个列表求它的所有不重复子集的问题。这个问题分为两类：一类是所给列表包含重复元素，另一类是所给列表不含重复元素。分别对应lintcode中17和18题。

### 1.列表不含重复元素的子集 ###

这里使用深度优先搜索的思想，递归求解。  
代码

class Solution {
    public:
        /**
         * @param nums: A set of numbers
         * @return: A list of lists
         */
    
        vector<vector<int> > results; 
    
        vector<vector<int>> subsets(vector<int> &nums) {
            // write your code here
            vector<int> result;
            int n = nums.size();
            if(n == 0){
                results.push_back(result);
                return results;
            }
    
            //排序
            sort(nums.begin(), nums.end());
            //递归求解
            rec(result, nums, 0, n);
    
            return results;
        }
    
        void rec(vector<int> &result, vector<int> &nums, int i, int n){
            //i == 0时，加入空集
            results.push_back(result);
            for(int j = i; j < n; j++){
                result.push_back(nums[j]);
                rec(result, nums, j+1, n);
                result.pop_back();
            }
        }
    };

### 2.列表中含有重复元素的子集 ###

由于有重复元素，所以在递归求解时每次都要进行去重。为了便于查找重复的元素，我们先将列表排序，排序后重复元素会相邻排列，之后只需在每次循环中增加一次判断即可去除重复元素。  
代码

class Solution {
    public:
        /**
         * @param nums: A set of numbers.
         * @return: A list of lists. All valid subsets.
         */
        vector<vector<int>> subsetsWithDup(vector<int> &nums) {
            // write your code here
            vector<vector<int> > results;
            vector<int> result;
            if(nums.size() == 0){
                results.push_back(result);
                return results;
            }
            //对数组排序
            sort(nums.begin(), nums.end());
            rec(results, result, nums, 0);
            return results;
        }
    
        void rec(vector<vector<int> > &results, vector<int> result, vector<int> nums, int i){
            results.push_back(result);
            for(int j = i; j < nums.size(); j++){
                //若该元素不是第一个，且与前一个元素相等，则判定为重复元素，跳过该次循环即可去重
                if(j != i && nums[j] == nums[j-1])
                    continue;
                result.push_back(nums[j]);
                rec(results, result, nums, j+1);
                result.pop_back();
            }
        }
    };