给定一个由不同整数构成的数组 nums 和一个整数 target ,请你从 nums 找出总和是 target 的组合的个数。解集中可以重复使用 nums 中的元素。且解集中数字顺序不同视为不同的组合。
数据范围: 数组长度满足 ,数组中的数满足 ,
[1,2,3],4
7
所有可能的组合为: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
[9],10
0
[9],18
1
[[9,9]]
public int combination (int[] nums, int target) { // write code here ArrayList<ArrayList<Integer>> res = new ArrayList<>(); ArrayList<Integer> list = new ArrayList<>(); Arrays.sort(nums); dfs(res, list, nums, target); return res.size(); } public void dfs(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list, int[] nums, int target) { if(target == 0){ res.add(new ArrayList<Integer>(list)); } for (int i = 0; i < nums.length; i++) { if (nums[i] > target) { return; } list.add(i); dfs(res, list, nums, target - nums[i]); list.remove(list.size() - 1); } }
public int combination (int[] nums, int target) { backTrack(nums, target); return cnt; } public int sum = 0, cnt = 0; public void backTrack(int[] nums, int target) { if (sum > target) return; if (sum == target) { cnt++; return; } for (int i = 0; i < nums.length; i++) { sum += nums[i]; backTrack(nums, target); sum -= nums[i]; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ int count = 0; public int combination (int[] nums, int target) { // write code here dfs(nums, target); return count; } private void dfs(int[] nums, int rest) { if(rest < 0){ return; // 凑过头了,本次组合无效 } if(rest == 0){ // 凑足目标值了就添加答案 count++; }else{ // 否则遍历此时选所有数的可能,继续递归选下一个数 for(int i = 0; i < nums.length; i++){ dfs(nums, rest - nums[i]); } } } }