Combination Sum [LeetCode]

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Problem Description: http://oj.leetcode.com/problems/combination-sum/

Basic idea: It seems complicate at first. But once I got the recursive idea, the solution was neat. This code could be not efficient. I will rewrite with dynamic programming next time.

 class Solution {

 public:

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

         // Note: The Solution object is instantiated only once and is reused by each test case.

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

         vector<vector<int> > combinations;

         for(int i = ; i < candidates.size(); i ++) {

             if(candidates[i] > target)

                 break;

             if(candidates[i] == target) {

                 vector<int> combination;

                 combination.push_back(candidates[i]);

                 combinations.push_back(combination);

             }else{

                 if(i ==  && target % candidates[i] != )

                     continue;

                 if(i ==  && target % candidates[i] == ){

                     vector<int> combination(target / candidates[i], candidates[i]);

                     combinations.push_back(combination);

                     continue;

                 }

                 vector<int> sub_candidates(candidates.begin(), candidates.begin() + i + );

                 vector<vector<int> > rests =  combinationSum(sub_candidates, target - candidates[i]);

                 for(auto item: rests){

                     item.push_back(candidates[i]);

                     combinations.push_back(item);

                 }

             }

         }

         return combinations;

     }

 };