暴力搜索
struct Node { vector<int> a; int sum; int index; Node(){} Node(int index,int sum,vector<int> a) { this->index = index; this->sum = sum; this->a = a; } }; class Solution { public: queue<Node> q; vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> ans; for(int i=0;i<candidates.size();i++) { vector<int> a; a.push_back(candidates[i]); q.push(Node(i,candidates[i],a)); } while(!q.empty()) { Node term = q.front(); q.pop(); if(term.sum==target) { ans.push_back(term.a); continue; } for(int i=term.index;i<candidates.size();i++) { if(term.sum+candidates[i]>target) continue; else if(term.sum+candidates[i]==target) { vector<int> x = term.a; x.push_back(candidates[i]); ans.push_back(x); } else { vector<int> x = term.a; x.push_back(candidates[i]); q.push(Node(i,term.sum+candidates[i],x)); } } } return ans; } };
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句