Java implements LeetCode (combined sum)
- 2021-10-15 10:32:19
- OfStack
leetcode topic
Sum of Combinations--leetcode 39
Title description
Given 1 array candidates without repeating elements and 1 target number target,
Find out all the combinations in candidates that can make the number sum target.
Numbers in candidates can be selected indefinitely and repeatedly.
Description:
All numbers (including target) are positive integers.
Solution sets cannot contain duplicate combinations.
Example 1:
Input: candidates = [2, 3, 6, 7], target = 7,
The set to be solved is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2, 3, 5], target = 8,
The set to be solved is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
Source: Force Buckle (LeetCode)
Link: https://leetcode-cn.com/problems/combination-sum
Copyright belongs to the collar button network. Please contact the official authorization for commercial reprinting, and please indicate the source for non-commercial reprinting.
Train of thought
Backtracking algorithm
Recursive summing is the combination of target, and the exit is sum exceeding target
Code
package com.leetcode.array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Title:
* Combination sum -- leetcode 39
*
* Title description:
*
Given 1 Array without repeating elements candidates And 1 Number of targets target ,
Find out candidates All the numbers in which you can make the sum of numbers to target The combination of.
candidates Numbers in can be selected indefinitely and repeatedly.
Description:
All figures (including target ) are positive integers.
Solution sets cannot contain duplicate combinations.
Example 1:
Input : candidates = [2,3,6,7], target = 7,
The set to be solved is :
[
[7],
[2,2,3]
]
Example 2:
Input : candidates = [2,3,5], target = 8,
The set to be solved is :
[
[2,2,2,2],
[2,3,3],
[3,5]
]
Source: Likou ( LeetCode )
Links: https://leetcode-cn.com/problems/combination-sum
Copyright belongs to the collar button network. Please contact the official authorization for commercial reprinting, and please indicate the source for non-commercial reprinting.
*/
public class CombinationSum {
/**
* Thoughts:
* 1 Backtracking algorithm
* 2 , recursively find the sum for target The combination of exports is and exceeds target
*/
public List<List<Integer>> combinationSum(int[] bb, int target) {
List<List<Integer>> res = new ArrayList<>();
if (bb == null) {
return res;
}
addCombinations(bb, 0, target, new ArrayList<Integer>(), res);
return res;
}
private void addCombinations(int[] bb, int start, int target, List<Integer> cache, List<List<Integer>> res) {
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(cache));
return;
}
for (int i=start; i<bb.length; i++) {
cache.add(bb[i]);
addCombinations(bb,i,target-bb[i],cache,res);
cache.remove(cache.size()-1);
}
}
/**
* Thoughts:
* Optimized backtracking
*/
public List<List<Integer>> combinationSumII(int[] bb, int target) {
List<List<Integer>> res = new ArrayList<>();
if (bb == null) {
return res;
}
// After sorting the array You can reduce the number of recursions when recursive, and cooperate with if (bb[i] > target) break;
Arrays.sort(bb);
addCombinationsII(bb, 0, target, new ArrayList<Integer>(), res);
return res;
}
private void addCombinationsII(int[] bb, int start, int target, List<Integer> cache, List<List<Integer>> res) {
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(cache));
return;
}
for (int i=start; i<bb.length; i++) {
// Match the sorted array Improve performance
if (bb[i] > target) {
break;
}
cache.add(bb[i]);
addCombinationsII(bb,i,target-bb[i],cache,res);
cache.remove(cache.size()-1);
}
}
}