首页 > 代码库 > Battery (Coin Change)
Battery (Coin Change)
Problem
电池有6节包装，9节包装，20节包装三种，input需要多少节电池，如果可以刚好用3种包装的凑到这个数，就输出这个解， 忘了是不是要输出所有的解。
e.g 输入20， 答{20} 输入17 答没有 输入18，那可能是{6,6,6}也可能是{9,9}。 有点像找钱的问题，似乎是从集合中找到所有集合值等于一个target这个题的简化版，因为集合只有6 9 20。
Solution
1 public static List<List<Integer>> combination(int[] num, int target) { 2 List<List<Integer>> res = new ArrayList<List<Integer>>(); 3 4 if(num == null || num.length == 0) return res; 5 6 List<Integer> path = new ArrayList<Integer>(); 7 helper(num, target, res, path); 8 return res; 9 10 }11 12 public static void helper(int[] num, int target, List<List<Integer>> res, List<Integer> path) {13 14 if(target == 0) {15 res.add(new ArrayList<Integer>(path));16 return;17 }18 19 if(target < 0)20 return;21 22 for(int i=0; i<num.length; i++) {23 path.add(num[i]);24 helper(num, target - num[i], res, path);25 path.remove(path.size() - 1);26 }27 }
Battery (Coin Change)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。