DP solution


  • 0
    D

    althought it seems stupid using dp, since it seems hard to get the set from the result..but, I finish it cost several hours(it due to my IQ)..Maybe it will be needed for some others..

    vector<vector<int>> combinationSum(vector<int>& candidates, int target)
    {
    	int n = candidates.size(), start = 0;
    	vector<vector<int>> dp(n + 1);
    	for (int i = 0; i <= n; i++)
    		dp[i] = vector<int>(target + 1, 0);
    	for (int i = 1; i <= n; i++)
    	{
    		for (int j = 1; j <= target; j++)
    		{
    			dp[i][j] = dp[i - 1][j];
    			if ((j - candidates[i - 1])>0)
    				dp[i][j] = dp[i - 1][j] + dp[i][j - candidates[i - 1]];
    			if (j == candidates[i - 1])
    				dp[i][j]++;
    		}
    	}
    	vector<vector<int>> res(dp[n][target]);
    	fun(res, dp, candidates, n, start, target);
    	return res;
    
    }
    void fun(vector<vector<int>> &res, vector<vector<int>> &dp, vector<int> &candidates, int i, int &start, int target)
    {
    	if (i <= 0 || target <= 0)
    		return;
    	if (candidates[i - 1] == target)
    		res[start++].push_back(candidates[i - 1]);
    	if ((target - candidates[i - 1]) >= 0 && dp[i][target - candidates[i - 1]])
    	{
    		for (int j = start; j < dp[i][target - candidates[i - 1]] + start; j++)
    			res[j].push_back(candidates[i - 1]);
    		fun(res, dp, candidates, i, start, target - candidates[i - 1]);
    	}
    	if (dp[i - 1][target])
    		fun(res, dp, candidates, i - 1, start, target);
    }
    

Log in to reply
 

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