即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

回溯法(leetcode-Combination Sum)

编程语言 drink_tea 16℃ 0评论

Given a set of candidate numbers (C(without duplicates) and a target number (T),
find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7


A solution set is: 

[
  [7],
  [2, 2, 3]
]

本题宜采用回溯法,代码如下:

#include
#include
#include
using namespace std;

void backTracking(vector> &res, vector &arr ,vectorcandidate ,int start,int target )
{
 if (target < 0)
 {
  return;
 }
 if (target == 0)
 {
  res.push_back(arr);
 }
 for (int i = start; i < candidate.size(); i++)
 {
  arr.push_back(candidate[i]);
  backTracking(res,arr,candidate,i,target-candidate[i]);
  arr.pop_back();
 }
}

int main()
{
 vector candidate = {2, 3, 6, 7};
 int target = 7;
 vector> res;
 vector arr;
 sort(candidate.begin(),candidate.end());
 backTracking(res, arr, candidate, 0, target);
 for (int i = 0; i < res.size(); i++)
 {
  for (int j = 0; j < res[i].size(); j++)
  {
   cout << res[i][j]<<" ";
  }
  cout << endl;
 }
 return 0;
}










转载请注明:CodingBlog » 回溯法(leetcode-Combination Sum)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情