给定一个正整数数组 nums[], 求所有可能的组合，使得组合中的元素和等于target, 例如: nums 为 {3, 4, 5}, target 为 9, 解为 {3, 3, 3}, {4, 5}
#include <algorithm>
#include <memory>
#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <stack>void backtrack(std::vector<int> &state, std::vector<int> &choices, int target, int total, int start, std::vector<std::vector<int>> &res)
{if (total == target){res.push_back(state);return;}for (int i = start; i < choices.size(); i++){int choice = choices[i];if (total + choice <= target){total += choice;state.push_back(choice);backtrack(state, choices, target, total, i, res);total -= choice;state.pop_back();}}
}int main()
{std::vector<int> choices = {3, 4, 5}; //setstd::vector<int> state{}; //subsetstd::vector<std::vector<int>> res{}; //resultint target = 9;int total = 0;int start = 0;backtrack(state, choices, target, total, start, res);for (auto vv : res){for (auto v : vv){std::cout << v << " ";}std::cout << "\n";}return 0;
}