题目
输入两个数 m、n,输出 [1, m] 范围内所有和为 n 的组合。
样例输入:5, 3
样例输出:[[1, 1, 1], [1, 2], [3]]
代码
说明:
如果要求组合内数字不重复,可以用 getResult(i+1, end, target-i, temp);
import java.util.ArrayList;
public class Solution{
private static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
public static void main(String[] args) {
int a = 5;
int b = 6;
ArrayList<Integer> temp = new ArrayList<>();
new Solution().getResult(1, a, b, temp);
System.out.println(result);
}
public void getResult(int start, int end, int target, ArrayList<Integer> temp) {
if (target == 0) {
ArrayList<Integer> tmp = new ArrayList<>(temp);
result.add(tmp);
return;
} else {
for (int i=start; i<=end; i++) {
if (i <= target) {
temp.add(i);
getResult(i, end, target-i, temp); // 数字有重复
//getResult(i+1, end, target-i, temp); // 数字不重复
temp.remove(temp.size() - 1);
} else {
return;
}
}
}
}
}
扩展
与这道题类似的有此题:加起来和为目标值的组合,这道题的解法也是受此题启发。
![](https://img-blog.csdnimg.cn/20210513120938614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ4MDA5NzU=,size_16,color_FFFFFF,t_70)
import java.util.ArrayList;
import java.util.Arrays;
public class SumTarget {
private ArrayList<ArrayList<Integer>> result = new ArrayList<>();
public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
if (num == null || num.length == 0 || target == 0) {
return result;
}
ArrayList<Integer> temp = new ArrayList<>();
Arrays.sort(num);
combinationSum(num, 0, num.length, target, temp);
return result;
}
private void combinationSum(int[] num, int start, int end, int target, ArrayList<Integer> temp) {
if (target == 0) {
ArrayList<Integer> copy = new ArrayList<>(temp);
result.add(copy);
return;
}
for(int i=start; i<end; i++) {
if (i>start && num[i] == num[i-1]) {
continue;
}
if (num[i] <= target) {
temp.add(num[i]);
combinationSum(num, i+1, num.length, target-num[i], temp);
temp.remove(temp.size()-1);
} else {
return;
}
}
}
public static void main(String[] args) {
SumTarget sumTarget = new SumTarget();
int[] num = new int[]{100, 10, 20, 70, 60, 10, 50};
int target = 80;
System.out.println(sumTarget.combinationSum2(num, target));
}
}