当前位置:   article > 正文

Java实现 LeetCode 组合总和(I-IV)(dfs)_leetcode 组合总和 java

leetcode 组合总和 java

共同特征:都是用一个数组凑出一个目标数,每道题的限制有些不同,都能够用 dfs+回溯+剪枝。传递一个sum参数,判断能否将新的数字加入到ans序列中。

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]
]

来源:力扣(LeetCode
链接:https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
		List<Integer> list = new LinkedList<>();
		Arrays.sort(candidates);//做一个排序,当前结点的无法组成目标值,那么比他大的数也不可能组成
		dfs(ans,list,target,candidates,target,0);
		return ans;
	}
	private void dfs(List<List<Integer>> ans, List<Integer> list, int sum, int[] candidates, int target, int index) {
		if(sum == 0) {
			ans.add(new ArrayList<Integer>(list));
		}
		for(int i = index; i < candidates.length; i++) {
			if(sum - candidates[i] < 0) {
				break;
			}
			list.add(candidates[i]);
			dfs(ans,list,sum-candidates[i],candidates,target,i);
			list.remove(list.size()-1);
		}
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

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]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
       List<List<Integer>> ans = new LinkedList<List<Integer>>();
		List<Integer> list = new LinkedList<>();
		
		Arrays.sort(candidates);
		dfs(ans,list,candidates,target,target,0);
		return ans;
	}
	private void dfs(List<List<Integer>> ans, List<Integer> list, int[] candidates, int target, int sum, 
			int k) {
		if(sum == 0) {
			ans.add(new LinkedList<>(list));
		}
		for(int i = k; i < candidates.length; i++) {
			if(sum-candidates[i] < 0) {
					break;
				}
				if(i > k && candidates[i] == candidates[i-1]) {//处理重复的情况
					continue;
				}
				
				list.add(candidates[i]);
				dfs(ans,list,candidates,target,sum-candidates[i],i+1);
				
				list.remove(list.size()-1);
			
		
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

216.组合总和III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

说明:

所有数字都是正整数。
解集不能包含重复的组合。
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> list = new ArrayList<Integer>();
		List<List<Integer>> ans = new ArrayList<>();
		dfs(n,list,ans,k,1);
		return ans;
    }
	private void dfs(int n, List<Integer> list, List<List<Integer>> ans, int k, int start) {
		if(n == 0) {
			if(list.size() == k) {
				ans.add(new ArrayList<>(list));
			}
		}
		for(int i = start; i <= 9; i++) {
			if(n-i >= 0 && list.size() < k && !list.contains(i)) {
				list.add(i);
				dfs(n-i, list, ans, k, i+1);
				list.remove(list.size()-1);
			}
		}
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

377.组合总和 IV
给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意,顺序不同的序列被视作不同的组合。

因此输出为 7。
进阶:
如果给定的数组中含有负数会怎么样?
问题会产生什么变化?
我们需要在题目中添加什么限制来允许负数的出现?

致谢:
特别感谢 @pbrother 添加此问题并创建所有测试用例。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-iv
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这道用的动态规划

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
		dp[0] = 1;

		for(int i = 1; i <= target; i++) {
			for(int j = 0; j < nums.length; j++) {
				if(i >= nums[j] && dp[i-nums[j]] > 0) {
					dp[i] += dp[i-nums[j]];
				}
			}
		}
		return dp[target];
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/476078
推荐阅读
相关标签
  

闽ICP备14008679号