【LeetCode】39. Combination Sum & 40. Combination Sum II分析及解法&DFS

一时失言乱红尘 2022-07-25 15:39 165阅读 0赞

39. Combination Sum

Total Accepted: 87334 Total Submissions: 283947 Difficulty: Medium

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. (ie, a1 ≤ a2 ≤ … ≤ ak).
 *  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]`

【题意】  
  
     从给定的数据集合中寻找合适的若干数据（可重复利用），使得这些数据之和等于目标值（target）  
  
  
【分析】  
  
    很显然，解此题需要用到深度优先搜索（Deepth First Search，DFS ），关于DFS的定义百度可以查到：[点击打开链接][Link 1]，本题中，由于数据可重复利用，我们需要注意循环中的搜索起点的设置。当搜索进行到数据集末端（类似二叉树搜索中的叶子节点），我们需要采用“回溯法”，返回一层继续搜索。  
  
【解法】

class Solution
    {
    public:
    	vector<vector<int>> combinationSum(vector<int>& nums, int target)
    	{
    		vector<int> temp;//存储可能满足要求的搜索路径
    		sort(nums.begin(),nums.end());//首先将数组进行升序排序
    		inputNumSet=nums;//复制输入数据集合
    		DFS(temp,target, 0);//从第一个元素开始深度优先搜索
    		return res;
    	}
    private:
    	vector<vector<int>> res;//存储所有满足要求的搜索路径，即满足要求的数据组合
    	vector<int> inputNumSet;//保存输入数据集
    
    
    	//计算当前搜索路径数据之和
    	int sumOfNums(vector<int>& temp)
    	{
    		int sum=0;
    		for(int i=0;i<temp.size();i++)
    		{
    			sum+=temp[i];
    		}
    		return sum;
    	}
    
    
    	//深度优先搜索
    	void DFS(vector<int>& temp, int target, int start)
    	{
    		int sum;
    		sum=sumOfNums(temp);//计算目前搜索路径数据之和
    		if(sum==target)
    		{
    			res.push_back(temp);//如果目前组合数据和与目标相等，则存入容器res
    			return;
    		}
    		else if(sum>target)
    		{
    			return;//如果目前组合已经大于目标值，则对此路径进行“剪枝”，直接返回，不再继续此路径
    		}
    		else
    		{
    			//如果当前组合数值比目标值小，则继续搜索
    			for(int i=start;i<inputNumSet.size();i++)
    			{
    				if(i!=start&&inputNumSet[i]==inputNumSet[i-1])//避免重复解，由于给定的数据集中可能存在相同数据，
    					continue;
    				temp.push_back(inputNumSet[i]);
    				DFS(temp,target,i);//由于数据可重复利用，继续搜索时，起始点依旧为i，如果不允许重复利用数据，这里应为i+1
    				temp.pop_back();//上面一句为递归调用，要么找到目标路径并存储而返回，要么路径不满足要求而返回。
    				                //返回之后，进行回溯，返回继续搜索
    			}
    		}
    	}
    
    
    };

40. Combination Sum II

Total Accepted: 65829   Total Submissions: 239855   Difficulty: Medium

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

For example, given candidate set `10,1,2,7,6,1,5` and target `8`,   
A solution set is:   
`[1, 7]`   
`[1, 2, 5]`   
`[2, 6]`   
`[1, 1, 6]`

【题意】  
  
     从给定的数据集合中寻找合适的若干数据（不可重复利用），使得这些数据之和等于目标值（target），然后返回所有可能的搜索路径。  
  
【分析】  
  
    此题和上面一题非常类似，解答方法基本一致，这里不再赘述，关键注意：如何避免重复解？  
  
【解法】

class Solution
    {
    public:
    	vector<vector<int>> combinationSum2(vector<int>& nums, int target)
    	{
    		vector<int> temp;//存放搜索路径
    		sort(nums.begin(),nums.end());//升序排序
    		inputNumSet=nums;//存放输入数据
    		DFS(temp,target,0);//进行深度优先搜索，求取目标路径并存入res容器
    		return res;
    	}
    private:
    	//【数据域】
    	vector<vector<int>> res;
    	vector<int> inputNumSet;
    
    
    	//【成员函数域】
    	//函数1：求取当前数据组合的和
    	int sumOfNums(vector<int>& temp)
    	{
    		int sum=0;
    		for(int i=0;i<temp.size();i++)
    			sum+=temp[i];
    		return sum;
    	}
    
    
    	//函数2：深度优先搜索，寻找和与目标值相等数据组合
    	void DFS(vector<int>& temp,int target,int start)
    	{
    		//if(start==inputNumSet.size())return;//搜索到叶子节点，返回
    		int sum;
    		sum=sumOfNums(temp);
    
    
    		if(sum==target)//搜索到目标路径，将当前路径存入结果容器，返回
    		{
    			res.push_back(temp);
    			return;
    		}
    		else if(sum>target)//当前路径结果超过目标值，返回
    		{
    			return;
    		}
    		else//当前路径结果小于目标值，则继续搜索
    		{
    			for(int i=start;i<inputNumSet.size();i++)
    			{
    				if(i!=start&&inputNumSet[i]==inputNumSet[i-1])//避免重复组合
    					continue;
    				temp.push_back(inputNumSet[i]);
    				DFS(temp,target,i+1);//递归调用，要么找到目标路径并存储而返回，要么路径不满足要求而返回
    				temp.pop_back();//返回之后，进行回溯，返回继续搜索
    			}
    		}
    	}
    };

[Link 1]: http://baike.baidu.com/link?url=vS0MJIINELwpDhtpni4LLlpWtLBFVWLXddu-aUDJBiYu6uQzwmyNs8nsWY2UWB_CZp8b-wClXQ_qK6RvlqCRn-YH5iW1leT_rxT2XVwXsam