It wrongs when candidates = [1], target = 1, but it runs well on VS.


  • 0
    J
       vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
    
            vector<vector<int> > result;
            
            std::sort (candidates.begin (), candidates.end ());
           
            combinationSum (candidates, 0, target, result);
            return result;
        }
    
    
    
    
      void combinationSum (const vector<int> &candidates, int index, int target, vector<vector<int>> &result)
        {
            if (target <= 0 || target < candidates [index]);
            {
                return;
            }
            
            if (index >= candidates.size ())
            {
                return; 
            }
            
           // add the cases that can be added directly 
            for (int j = index; j < candidates.size (); j++)
            {
                if (target % candidates[j] == 0)
                {
                    vector<int> tmp (target/candidates[j], candidates[j]);
                    result.push_back (tmp);
                }
            }
            
              // add the case that can add the current number 
             int count  = target / candidates [index];
             for (int k = 1; k <= count; k++)
             {
                 vector<vector<int>> tmp_ret;
             
                 combinationSum (candidates, index + 1, target - k * candidates [index], tmp_ret);
                 
                 for (int i =0; i < (tmp_ret).size (); i++)
                 {
                     vector<int> tmp (k,candidates [index]);
                     
                     tmp.insert (tmp.end(), (tmp_ret)[i].begin (), (tmp_ret)[i].end());
                     result.push_back (tmp);
                 }
             }
          
              // add the cases that does not contain this number.
             vector<vector<int>> tmp_ret_test;
             combinationSum (candidates, index + 1, target, tmp_ret_test);
             
             if (tmp_ret_test.size () > 0)
             {
               for (int i = 0; i < (tmp_ret_test).size (); i++)
                 {
                     result.push_back ((tmp_ret_test)[i]);
                 }
             }
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.