LeetCode 78 子集 - 回溯解法

https://leetcode.cn/problems/subsets/description/

答案角度：for循环。

与组合问题不太一样, 不变的流程: 从index到最后选一个值(index为 i )加入path，接着再从 i+1 到最后选一个值加入 path.


for(int i = index; i<size; i++){
	path.push(loc[i])
	//再从 i+1 到 最后 选值加入
	add_path(i+1);
	path.pop();
}

👍 特殊的点: 这里result 保存的条件，因为每个子集都要加入， 只要path长度大于1，就要加入 result，但是不要 return(以往的题都是直接return，不继续加path了，)，这里还要继续遍历.

那么，递归算法不return 会无限执行下去吗? 不会，

最后一层，里面的for 循环不会执行， 所以不会继续进行深层次的调用，所以直接就返回上层了. 递归函数不一定要有 return 表达式，没有也可以不无限调用.

class Solution {

public:

    vector<int> loc_nums;

    vector<int> path;

    vector<vector<int>> result;

    void add_path(int index){

        if(path.size()>0){

            result.push_back(path);

        }

        for(int i = index;i<loc_nums.size();i++){

            path.push_back(loc_nums[i]);

            add_path(i+1);

            path.pop_back();

        }

    }

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

        loc_nums = nums;

        add_path(0);

        vector<int> null_vec;

        result.push_back(null_vec);

        return result;

    }

	};

本层输入角度：选或不选

对于一层的输入 index，本层都可以选或不选。

class Solution {

public:

    vector<int> loc_nums;

    vector<int> path;

    vector<vector<int>> result;

    void add_path(int index){
		//判断终点和之前的不一样，这里要走到尽头才能保存结果。
        if(index==loc_nums.size()){

            result.push_back(path);

            return;

        }
		//选
        path.push_back(loc_nums[index]);

        add_path(index+1);

        path.pop_back();

		//不选
        add_path(index+1);

    }

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

        loc_nums = nums;

        add_path(0);

        vector<int> null_vec;

        // result.push_back(null_vec);

        return result;

    }

};