Day15-递归&回溯-无重复数组的子集

BUPTrenyi

发布于 2019-07-15 08:58:23

44200

代码可运行

文章被收录于专栏：算法其实很好玩算法其实很好玩

运行总次数：0

代码可运行

一唠嗑

我又拖更了，我出来挨打了

本来昨天题的代码都写完了，但pm姐姐说，这个需求明天必须上，没办法，昨天就没时间写文章了

然后就是，从今天开始，开始递归+回溯的算法题

然后这周保证天天更！

二上题吧！

Q：已知一个数组，无重复元素，求能组成的所有子集。

举例：对于nums = 【1,2,3】

那么就要返回[ [], [1], [1,2], [1,2,3], [1,3], [2,3], [2], [3]]

三冷静分析

此时你脱口而出，遍历一遍不就行了，这题也拿来面我，渣渣

那你一定没动手码，因为这样很困难

我们一趟遍历完，只能得到[[1], [1,2], [1,2,3]]这样的子集，和单个数字的子集，因为我们没办法遍历到某个位置，往回遍历来取其他子集。

那怎么做啊

不卖关子，也节省一下时间，引入递归的概念：

一句话概括就是，函数自己调用自己，也叫递归调用

再引入个概念，回溯：

当遍历/前进到某个位置，无法满足要求，就回退一步重新选择。这种走不通就回退的方法，叫回溯。

好，回到题目。我们可以这样处理逻辑：

利用回溯算法，生成子集。即对于每个元素，都有试探放入或不放入。

先选择放入该元素，递归地进行后续元素的选择，完成放入该元素后续所有元素的试探；

然后将该元素拿出，进行一次，不放入该元素时，递归地进行后续元素的选择。

四完整代码及注释

//
// Created by renyi on 2019/6/24.
//
#include <iostream>
#include <vector>
using namespace std;

void findSubsets(int i, vector<int> &nums, vector<int> &item, vector<vector<int>> &result){
    if (i >= nums.size()){
        return;
    }
    item.push_back(nums[i]);//将nums的每个元素放入数组item
    result.push_back(item);//将item数组，放入最后的二维数组result
    findSubsets(i + 1, nums, item, result);//放入一个元素后，递归进行后续元素的选择
    item.pop_back();//将该元素拿出来
    findSubsets(i + 1, nums, item, result);//再递归跑一次，不放入该元素的情况下，对于后续元素的处理
}

vector<vector<int>> subsets(vector<int> &nums){
    vector<vector<int>> result;//最终结果，二维数组
    vector<int> item;//一维数组item
    result.push_back(item);
    findSubsets(0, nums, item, result);
    return result;
}

int main(){
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(3);
    vector<vector<int>> result;
    result = subsets(nums);
    for (int i = 0; i < result.size(); i++) {
        if (result[i].size() == 0){
            printf("[]");
        }
        for (int j = 0; j < result[i].size(); j++) {
            printf("[%d]", result[i][j]);
        }
        printf("\n");
    }
    return 0;
}