Subsets LeetCode总结

2023-01-29 13:32:20

Subsets

题目

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,

If nums = [1,2,3], a solution is:

[

[3],

[1],

[2],

[1,2,3],

[1,3],

[2,3],

[1,2],

[]

]

思路

一开始的想法首先就是回溯，每个元素都有两种选择；

题解

这道题的解法非常多，可以用来学习回溯的思想；

1. 增量构造法-递归版

代码

/**

 *  注意：不能根据path的size进行收敛，因为path数组的size不一定要和nums的size相等

 *  毕竟题目求的是子集，[]也是子集

 *  拥有两个递归，前者递归用来处理每一个nums中的值，后者递归用来处理前者的值为前提下，添加nums剩余的值

 *

 *  @param nums   <#nums description#>

 *  @param path   <#path description#>

 *  @param result <#result description#>

 *  @param step   <#step description#>

 */

void helper(const vector<int>& nums, vector<int>& path, vector<vector<int>>& result, int step) {

    // 收敛条件

    if (step == nums.size()) {

        result.push_back(path);

        return ; // 需要加上，否则将会执行下面的

    }

    // 不选当前字符

    helper(nums, path, result, step + 1);

    // 选当前字符

    path.push_back(nums[step]);

    helper(nums, path, result, step + 1);

    path.pop_back();

}

vector<vector<int>> subsets1(vector<int>& nums) {

    sort(nums.begin(), nums.end()); // 输出要求有序

    vector<vector<int>> result;

    vector<int> path;

    helper(nums, path, result, 0);

    return result;

}

用图简要介绍一下流程：

增量构造法，深搜，时间复杂度为o(2^n)，空间复杂度o(n);

2. 增量构造法-迭代版

/**

 *  增量构造法－迭代版

 *  这个方法的思路其实是，不断的复制前面的数组，再往这些新加入的数组分别加入新的值

 *

 *  @param nums <#nums description#>

 *

 *  @return <#return value description#>

 */

vector<vector<int>> subsets2(vector<int>& nums) {

    sort(nums.begin(), nums.end());

    vector<vector<int>> result(1);

    for (auto elem : nums) {

        // 请求两倍的内存空间

        result.reserve(result.size() * 2);

        // 获取之前的数据到达的位置

        auto half = result.begin() + result.size();

        // 赋值之前的数组

        copy(result.begin(), half, back_inserter(result));

        // 往新添加的数组加入新值

        for_each(half, result.end(), [&elem](decltype(result[0]) &e) {

            e.push_back(elem);

        });

    }

    return result;

}

解释一下上面的做法：

迭代版，时间复杂度o(2^n)，空间复杂度o(1)

3. 位向量法-递归版

/**

 *  位向量法

 *  使用step去控制数组中的哪个下标的值是否可以被选中，即加入数组

 *

 *  @param nums     <#nums description#>

 *  @param result   <#result description#>

 *  @param selected <#selected description#>

 *  @param step     <#step description#>

 */

void helper3(vector<int>& nums, vector<vector<int>>& result, vector<bool>& selected, int step) {

    if (step == nums.size()) {

        vector<int> subset;

        for (int i = 0; i < nums.size(); ++i) {

            if (selected[i]) {

                subset.push_back(nums[i]);

            }

            result.push_back(subset);

            return ;

        }

    }

    // 不选nums[step]

    selected[step] = false;

    helper3(nums, result, selected, step + 1);

    // 选nums[step]

    selected[step] = true;

    helper3(nums, result, selected, step+ 1 );

}

vector<vector<int>> subsets3(vector<int>& nums) {

    sort(nums.begin(), nums.end());

    vector<vector<int>> result;

    vector<bool> selected(nums.size(), false);

    helper3(nums, result, selected, 0);

    return result;

}

开一个位向量 bool selected[n]，每一个元素都可以选或者不选；

位向量法，深搜，和第一个方法类似，时间复杂度为o(2^n)，空间复杂度o(n)

4. 二进制法

/**

 *  二进制法（优化版的位向量法）

 *  第i位为1，表明选择nums[i]，为0则不选择

 *  比如011，则表示子集{2,3}

 *

 *  @param nums <#nums description#>

 *

 *  @return <#return value description#>

 */

vector<vector<int>> subsets4(vector<int>& nums) {

    sort(nums.begin(), nums.end());

    vector<vector<int>> result;

    const size_t n = nums.size();

    vector<int> v;

    // 1 << n 表示的是2 ^ n，组合的个数

    for (size_t i = 0; i < 1 << n ; ++i) {

        // 进行与操作,如果该位数为1，则加入数组

        for (size_t j = 0; j < n; ++j) {

            if (i & 1 << j) v.push_back(nums[j]);

        }

        result.push_back(v);

        v.clear();

    }

    return result;

}

二进制法，时间复杂度为o(2^n)，空间复杂度o(1)

5. DFS

/**

 *  dfs的实现思想

 *  只要数组中还存在值，则往里递归

 *

 *  @param nums   <#nums description#>

 *  @param result <#result description#>

 *  @param path   <#path description#>

 *  @param start  <#start description#>

 */

void dfs(vector<int> nums, vector<vector<int>>& result, vector<int>& path, int start) {

    result.push_back(path);

    for (int i = start; i < nums.size(); ++i) {

        path.push_back(nums[i]);

        dfs(nums, result, path, i + 1);

        path.pop_back();

    }

}

vector<vector<int>> subsets5(vector<int>& nums) {

    vector<vector<int>> result;

    if (nums.size()  <= 0) return result;

    vector<int> path;

    sort(nums.begin(), nums.end());

    dfs(nums, result, path, 0);

    return result;

}

DFS，时间复杂度为o(2^n)，空间复杂度o(n)

Subsets II

题目

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,

If nums = [1,2,2], a solution is:

[

[2],

[1],

[1,2,2],

[2,2],

[1,2],

[]

]

题解

因为题意是相似的，所以只需要处理重复存在值，这样返回的结果就不会出现重复的数组;

1. 判断前后是否相等

/**

 *  因为已经排了序，所以只需要判断是否相等

 *

 *  @param nums   <#nums description#>

 *  @param result <#result description#>

 *  @param path   <#path description#>

 *  @param start  <#start description#>

 */

void dfs(vector<int> nums, vector<vector<int>>& result, vector<int>& path, int start) {

    result.push_back(path);

    for (int i = start; i < nums.size(); ++i) {

        if (i != start && nums[i] == nums[i-1])

            continue;

        path.push_back(nums[i]);

        dfs(nums, result, path, i + 1);

        path.pop_back();

    }

}

vector<vector<int>> subsetsWithDup1(vector<int>& nums) {

    vector<vector<int>> result;

    if (nums.size()  <= 0) return result;

    vector<int> path;

    sort(nums.begin(), nums.end());

    dfs(nums, result, path, 0);

    return result;

}

另一种写法：

/**

 *  也是根据判断前后是否相等的情况

 *

 *  @param nums <#nums description#>

 *

 *  @return <#return value description#>

 */

vector<vector<int>> subsetsWithDup4(vector<int>& nums) {

    sort(nums.begin(), nums.end());

    vector<vector<int> > result(1);

    size_t previous_size = 0; // 保存之前的size

    for (size_t i = 0; i < nums.size(); ++i) {

        const size_t size = result.size();

        for (size_t j = 0; j < size; ++j) {

            // i等于0的情况是因为满足单独一个数的情况

            if (i == 0 || nums[i] != nums[i-1] || j >= previous_size) {

                result.push_back(result[j]);

                result.back().push_back(nums[i]);

            }

        }

        previous_size = size;

    }

    return result;

}

2. 统计个数，记录位置

/**

 *  step控制的是elems，而不是nums，因为有重复值

 *

 *

 *  @param vector<pair<int <#vector<pair<int description#>

 *  @param elems           <#elems description#>

 *  @param step            <#step description#>

 *  @param path            <#path description#>

 *  @param result          <#result description#>

 */

void subsets(const vector<pair<int, int>> & elems, size_t step, vector<int> &path, vector<vector<int>>& result) {

    if (step == elems.size()) {

        result.push_back(path);

        return ;

    }

    for (int i = 0; i <= elems[step].second; ++i) {

        for (int j = 0; j < i; ++j) {

            path.push_back(elems[step].first);

        }

        subsets(elems, step + 1, path, result);

        for (int j = 0; j < i; ++j) {

            path.pop_back();

        }

    }

}

//    void subsets(const vector<int> nums, unordered_map<int, int>& count_map, int step, vector<int> &path, vector<vector<int>>& result) {

//        if (step == count_map.size()) {

//            result.push_back(path);

//            return ;

//        }

//

//        for (int i = 0; i <= count_map[nums[step]]; ++i) {

//            for (int j = 0; j < i; ++j) {

//                path.push_back(nums[step]);

//            }

//            subsets(nums, count_map, step + 1, path, result);

//            for (int j = 0; j < i; ++j) {

//                path.pop_back();

//            }

//        }

//    }

vector<vector<int>> subsetsWithDup2(vector<int>& nums) {

    vector<vector<int> > result;

    sort(nums.begin(), nums.end());

    unordered_map<int, int> count_map;

    // 用map记录每个元素的出现次数

    for_each(nums.begin(), nums.end(), [&count_map](int e) {

        if (count_map.find(e) != count_map.end())

            count_map[e]++;

        else

            count_map[e] = 1;

    });

    // 将map里的pair拷贝到一个vector中

    vector<pair<int, int> > elems;

    for_each(count_map.begin(), count_map.end(), [&elems](const pair<int, int> &e) {

        elems.push_back(e);

    });

    sort(elems.begin(), elems.end());

    vector<int> path;

    subsets(elems, 0, path, result);

    return result;

}

这道题的原型就是上面的第5种方法DFS，只不过是增加了unordered_map记录每个数据的个数.

另一种做法：

/**

 *  和上面的思想是一样的

 *  都是统计个数，记录位置

 *  后者只是用selected先保存下来，在收敛条件里面进行遍历加入

 *  这种方法有个很大的问题，因为使用的数组下标纪录位置

 *  当nums中的值足够大的时候，会造成大量的空间浪费，所以推荐使用unordered_map，就是上面的做法

 *

 *  @param nums     <#nums description#>

 *  @param count    <#count description#>

 *  @param selected <#selected description#>

 *  @param step     <#step description#>

 *  @param result   <#result description#>

 */

void subsets3(const vector<int> &nums, vector<int>& count, vector<int>& selected, size_t step, vector<vector<int> > & result) {

    if (step == count.size()) {

        vector<int> path;

        for (int i = 0; i < selected.size(); ++i) {

            for (int j = 0; j < selected[i]; ++j) {

                path.push_back(i + nums[0]);

            }

        }

        result.push_back(path);

        return ;

    }

    // 根据每个值对应的个数决定遍历次数 d

    for (int i = 0; i <= count[step]; i++) {

        selected[step] = i;

        subsets3(nums, count, selected, step + 1, result);

    }

}

vector<vector<int>> subsetsWithDup3(vector<int>& nums) {

    vector<vector<int> > result;

    sort(nums.begin(), nums.end());

    vector<int> count(nums.back() - nums.front() + 1, 0);

    // 计算所有元素的个数

    for (auto n : nums) {

        count[n - nums[0]]++;

    }

    // 每个元素选择多少个

    vector<int> selected(nums.back() - nums.front() + 1, -1);

    subsets3(nums, count, selected, 0, result);

    return result;

}

3. 用Set去重

/**

 *  用set去重

 *

 *  @param nums <#nums description#>

 *

 *  @return <#return value description#>

 */

vector<vector<int>> subsetsWithDup5(vector<int>& nums) {

    sort(nums.begin(), nums.end());

    // 用set去重，不能用unordered_set，因为输出有序

    set<vector<int> > result;

    const size_t n = nums.size();

    vector<int> path;

    // 如果哪位上为1，代表其应该加进来，则加进来

    for (size_t i = 0; i < 1 << n; ++i) {

        for (size_t j = 0; j < n; ++j) {

            if (i & 1 << j) {

                path.push_back(nums[j]);

            }

        }

        result.insert(path);

        result.clear();

    }

    vector<vector<int> > real_result;

    copy(result.begin(), result.end(), back_inserter(real_result));

    return real_result;

}

Ending~

码农公寓