元素无重复,可重复选,组合问题,可采用回溯算法并进行剪枝即可,具体如下:
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); ArrayList<Integer> track = new ArrayList<>(); int sum = 0; public ArrayList<ArrayList<Integer>> combinationCount (int target, int[] nums) { backtrack(0,target,nums); return res; } private void backtrack(int start,int target,int[] nums){ if(sum == target){ res.add(new ArrayList(track)); return; } if(sum > target){ return; } for(int i = start;i<nums.length;i++){ sum += nums[i]; track.add(nums[i]); backtrack(i,target,nums); sum -= nums[i]; track.remove(track.size()-1); } } }