递归&回溯-子集之和

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

void findSubsetsSum(int i, vector<int> &nums, vector<int> &item, vector<vector<int>> &result, set<vector<int>> &res_set, int sum, int target){
    if (i >= nums.size() || sum > target){//sum是当前item中元素的和，一旦大于了target，比如10 > 8,就不在递归回溯了，即，剪枝
        return;
    }

    sum += nums[i];//累加sum
    item.push_back(nums[i]);//追加进临时数组item

    if (res_set.find(item) == res_set.end() && sum == target){//item没在集合中，且sum==target，即找到了和是target的子集
        result.push_back(item);//追加结果和集合
        res_set.insert(item);
    }
    findSubsetsSum(i + 1, nums, item, result, res_set, sum, target);
    sum -= nums[i];//回溯时，sum要减去nums【i】并从item中删除nums【i】
    item.pop_back();
    findSubsetsSum(i + 1, nums, item, result, res_set, sum, target);
}

vector<vector<int>> subsets(vector<int> &nums, int target){
    vector<vector<int>> result;
    vector<int> item;
    set<vector<int>> res_set;
    sort(nums.begin(), nums.end());//和上道题一样，依然先排序
    findSubsetsSum(0, nums, item, result, res_set, 0, target);
    return result;
}

int main(){
    vector<int> nums;
    nums.push_back(10);
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(7);
    nums.push_back(6);
    nums.push_back(1);
    nums.push_back(5);
    vector<vector<int>> result;
    result = subsets(nums, 8);
    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;
}