Leetcode: Combination Sum (16ms) Analysis & solution

PROBLEM:

Given a set of candidate numbers (C) 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.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. 
• 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]

Analysis:

A backtracking problem. 

Initially I was totally comfused how to implement this one with backtracking. So I draw a procedure to see how the backtracking work in this case. After this drawing, it's really clear how to do it and how to optimized it in terms of time. See the figure below if you have trouble in understanding the BT for this problem. 

Identify the return conditions first. Then the backtracking part. Also how to optimize it by removing the "unnecessary implementations" in the figure. 

////////////////////////////////////////////////////////

//codes 16ms

class Solution {

public:

       vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

              //vector<int> input=candidates;

              vector<vector<int>> result;

              vector<int> tmp;

              int sum = 0, i = 0;

              sort(candidates.begin(), candidates.end());

              search(candidates, result, target, sum, tmp, i);

              return result;

       }

       void search(vector<int> &input, vector<vector<int>> &result, int target, int sum, vector<int> &tmp, int i){

              //return condition 1

              if (sum>target){

                     return;

              }

              //return condition 2

              else if (sum == target){

                     result.push_back(tmp);

                     return;

              }

              //backtracking

              else{

                     for (; i<input.size(); i++){

                           sum += input[i];

                           tmp.push_back(input[i]);

                           if (sum>target) i = input.size();//remove the unnecessary implementations 

                           search(input, result, target, sum, tmp, i);

                           tmp.pop_back();

                           sum -= input[i];

                     }

              }

       }

};