本文主要是介绍LeetCode--40. Combination Sum II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:https://leetcode.com/problems/combination-sum-ii/
这个题目是在39. Combination Sum加了点变化,就是说被选数组里的数可以重复的,但是同一个数组位置上的数不能重复选,不并且不同数组位置上选择的相同的数导致的相同的组合结果应该被剔除,比如最终结果[1,2,1]和[1,1,2]应该只保留一个。
这个题目我首先那想到的是在39拿到题目上做些微调,然后用HashSet将已经选择的组合转成字符存进去,然后利用它判重,如果重复就丢弃,否则加入到集合中并添加到最终返回的list中。这里需要先把原数排序使得得到的每个答案有序然后转为数字字符串,这个方法是有点蠢笨的,但是容易想到。
class Solution {public static List<List<Integer>> ret;public static int[] record=new int[100000];public static HashSet<String> set;public static List<List<Integer>> combinationSum2(int[] candidates, int target) {ret=new LinkedList<>();set=new HashSet<>();Arrays.sort(candidates);recursive(candidates,-1,target,0);return ret;}public static void recursive(int[] candidates,int idx,int target,int length){if(target==0){StringBuilder sb=new StringBuilder();for(int i=0;i<length;i++)sb.append(record[i]);String st=sb.toString();if(set.contains(st))return;else{set.add(st);LinkedList<Integer> tmp=new LinkedList();for(int i=0;i<length;i++)tmp.add(record[i]);ret.add(tmp);return;}}if(target<0 || idx>=candidates.length)return;for(int i=idx+1;i<candidates.length;i++){record[length]=candidates[i];recursive(candidates,i,target-candidates[i],length+1);}}
}
效率当然较低,beat 14.26%!有时间再来看看高效的解法:
这篇关于LeetCode--40. Combination Sum II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!