本文主要是介绍Leetcode 039 Combination Sum（隐式图搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接：Leetcode 039 Combination Sum
解题思路：隐式图搜索，状态包括当前使用到的数值下标（对应值一定使用过），和剩余的和。每次枚举当前下标往后的一个数，并枚举使用它的个数，对每个合理状态插入队列。而当剩余的和为零时，记录答案。
class Solution {public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> tmp;vector<vector<int>> ans;queue< pair<int, int> > que_infos;queue<vector<int>> que_state;que_infos.push(make_pair(target, 0));que_state.push(tmp);sort(candidates.begin(), candidates.end());while (!que_infos.empty()) {int res = que_infos.front().first;int start = que_infos.front().second;vector<int> state = que_state.front();que_infos.pop(), que_state.pop();if (res == 0) { ans.push_back(state); continue;}for (int i = start; i < candidates.size(); i++) {if (candidates[i] > res) break;tmp = state;tmp.push_back(candidates[i]);que_infos.push(make_pair(res - candidates[i], i));que_state.push(tmp);}}return ans;}
};
这篇关于Leetcode 039 Combination Sum（隐式图搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
