✔[39]组合总和 & [40]组合总和 II

刺骨的言语ヽ痛彻心扉 2021-06-22 15:38 352阅读 0赞

### ✔\[39\]组合总和 ###

//给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。  
//  
// candidates 中的数字可以无限制重复被选取。  
//  
// 说明：  
// 所有数字（包括 target）都是正整数。  
// 解集不能包含重复的组合。  
//  
// 示例 1：  
// 输入：candidates = \[2,3,6,7\], target = 7,  
//所求解集为：  
//\[  
// \[7\],  
// \[2,2,3\]  
//\]  
//  
// 示例 2：  
// 输入：candidates = \[2,3,5\], target = 8,  
//所求解集为：  
//\[  
// \[2,2,2,2\],  
// \[2,3,3\],  
// \[3,5\]  
//\]  
//  
// 提示：  
// 1 <= candidates.length <= 30  
// 1 <= candidates\[i\] <= 200  
// candidate 中的每个元素都是独一无二的。  
// 1 <= target <= 500  
//  
// Related Topics 数组 回溯算法

import java.util.List;
    import java.util.ArrayList;
    class Solution { 
    	public List<List<Integer>> combinationSum(int[] candidates, int target) { 
    		List<List<Integer>> res = new ArrayList<>();
    		if (candidates.length < 1 && target < 1) { 
    			return res;
    		}
    		dfs(candidates, target, 0, new ArrayList<Integer>(), res);
    		return res;
    	}
    
    	private void dfs(int[] candidates, int target, int start, List<Integer> targetArr, List<List<Integer>> res) { 
    		// 递归出口，如果数组和大于等于target
    		if (sumOfArr(targetArr) >= target) { 
    			// 如果相等，记录结果
    			if (sumOfArr(targetArr).equals(target)) { 
    				res.add(new ArrayList<>(targetArr));
    			}
    			return;
    		}
    
    		for (int i = start; i < candidates.length; i++) { 
    			targetArr.add(candidates[i]);
    			dfs(candidates, target, i, targetArr, res);
    			targetArr.remove(targetArr.size() - 1);
    		}
    	}
    
    	private Integer sumOfArr(List<Integer> targetArr) { 
    		return targetArr.stream().mapToInt(i -> i).sum();
    	}
    }

结果不理想：

解答成功:
    			执行耗时:72 ms,击败了5.05% 的Java用户
    			内存消耗:40.4 MB,击败了9.64% 的Java用户

看了别人写的，在计算当前数组和的时候做了优化，不要每次计算总和：  
稍作修改：

import java.util.List;
    import java.util.ArrayList;
    
    class Solution { 
    	public List<List<Integer>> combinationSum(int[] candidates, int target) { 
    		List<List<Integer>> res = new ArrayList<>();
    		if (candidates.length < 1 && target < 1) { 
    			return res;
    		}
    		dfs(candidates, target, 0, new ArrayList<Integer>(), res);
    		return res;
    	}
    
    	private void dfs(int[] candidates, int target, int start, List<Integer> targetArr, List<List<Integer>> res) { 
    		// 递归出口，需要的数字小于0或等于0
    		if (target < 0) return;
    		// 如果需要的数字为0，说明已经相等
    		if (target == 0) { 
    			res.add(new ArrayList<>(targetArr));
    			return;
    		}
    		for (int i = start; i < candidates.length; i++) { 
    			targetArr.add(candidates[i]);
    			dfs(candidates, target - candidates[i], i, targetArr, res);
    			targetArr.remove(targetArr.size() - 1);
    		}
    	}
    }

解答成功:
    			执行耗时:4 ms,击败了55.57% 的Java用户
    			内存消耗:39.8 MB,击败了91.14% 的Java用户

基本可以了。有时古板的思路就是费事

### \[40\]组合总和 II ###

//给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。  
//  
// candidates 中的每个数字在每个组合中只能使用一次。  
// 说明：  
// 所有数字（包括目标数）都是正整数。  
// 解集不能包含重复的组合。  
//  
// 示例 1:  
// 输入: candidates = \[10,1,2,7,6,1,5\], target = 8,  
//所求解集为:  
//\[  
// \[1, 7\],  
// \[1, 2, 5\],  
// \[2, 6\],  
// \[1, 1, 6\]  
//\]  
// 示例 2:  
//  
// 输入: candidates = \[2,5,2,1,2\], target = 5,  
//所求解集为:  
//\[  
// \[1,2,2\],  
// \[5\]  
//\]  
// Related Topics 数组 回溯算法  
在39题的基础上，40题要求每个数字只能使用一次，而且candidate 中的元素是可能重复的，代码看注释

import java.util.Arrays;
    class Solution { 
    	public List<List<Integer>> combinationSum2(int[] candidates, int target) { 
    		List<List<Integer>> res = new ArrayList<>();
    		if (candidates.length < 1 && target < 1) { 
    			return res;
    		}
    		// 针对candidates存在重复元素，采用先排序，再过滤
    		Arrays.sort(candidates);
    		dfs(candidates, target, 0, new ArrayList<Integer>(), res);
    		return res;
    	}
    
    	private void dfs(int[] candidates, int target, int start, List<Integer> targetArr, List<List<Integer>> res) {  
    		// 递归出口，需要的数字小于0或等于0
    		if (target < 0) return;
    		// 如果需要的数字为0，说明已经相等
    		if (target == 0) { 
    			res.add(new ArrayList<>(targetArr));
    			return;
    		}
    		for (int i = start; i < candidates.length; i++) { 
    			// 针对candidates存在重复元素，采用先排序，再过滤 i>start 是为了当i==start时要保留相同元素，当i>start时，重复元素就跳过了
    			if (i > start && candidates[i] == candidates[i - 1]) continue;
    			targetArr.add(candidates[i]);
    			// 针对元素不能重复，每次迭代需要+1
    			dfs(candidates, target - candidates[i], i + 1, targetArr, res);
    			targetArr.remove(targetArr.size() - 1);
    		}
    	}
    }