My Solution without using recursive(19ms) with C++


  • 0
    P
    class Solution {
    public:
    	vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
    		vector<vector<int> > result; vector<int> Data;
    		sort(candidates.begin(), candidates.end());
    		int i = 0; int remain = target;
    		while( i<candidates.size() ) {
            	if(remain <= candidates[i]) {
            		if(remain==candidates[i]){
            		    Data.push_back(i);
            			result.push_back(Data); 
            			Data.pop_back(); 
            		}
            		if(!Data.empty()) {
            			remain += candidates[Data.back()];  
            			i=Data.back()+1;
            			Data.pop_back(); 
            			while(i==candidates.size() && !Data.empty()) {
            				remain +=candidates[Data.back()];
            				i=Data.back()+1;
            				Data.pop_back();
            			}
            		} else break;
            	}
    			else {
    				remain -= candidates[i];
    				Data.push_back(i);
    			}
    		}
    		for(int i=0; i<result.size(); i++) 
    			for(int j=0; j<result[i].size(); j++)
    				result[i][j] = candidates[result[i][j]];
    		return result;
    	}
    };

  • 0
    M

    The solution set contains duplicate combinations when giving {2,2} to find 4


  • 0
    P

    Yes, you're right! When the candidates' data have the duplicate data, the code will process the duplicate cases!! But in this solution, it have the notes that "The candidates'data did not have the duplicate data". So, have no need to worry about it.


  • 0
    M

    Yes, I understand what do you mean. But it seems that there aren't any word to say "The candidates'data did not have the duplicate data", so I commented to you. And I have sent a feedback to the admin.


Log in to reply
 

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