public List<List<Integer>> combinationSum(int[] candidates, int target)?{? ? List<List<Integer>> res = new ArrayList<>();? ? Arrays.sort(candidates);? ? ? ??? ? helper(candidates, target, res, new ArrayList<>(), 0);? ? ? ??? ? return res;}?private void helper (int[] candidates, int target, List<List<Integer>> res, List<Integer> temp, int index) {? ? if( target < 0) return;? ? if(target == 0) {? ? ? ? res.add(new ArrayList<>(temp));? ? ? ? return;? ? }? ? for(int i = index; i < candidates.length; i++) {? ? ? ? if(candidates[i] > target) {? ? ? ? ? ? return;? ? ? ? }? ? ? ? temp.add(candidates[i]);? ? ? ? helper(candidates, target - candidates[i], res, temp, index);? ? ? ? temp.remove(temp.size() - 1);? ? }}For an input: candidates = [2,3,6,7], and target = 7My output is: [[2,2,3],[2,3,2],[3,2,2],[7]]Correct Output: [[2,2,3],[7]]顯然，我需要在添加到結果之前檢查重復項。我知道我可以創建一組字符串，其中每個字符串都是列表的排序版本，例如 [2,3,2] => “223”。這將幫助我檢查是否需要將列表添加到結果中。我的問題是在我的情況下檢查重復項的最佳方法是什么？
4 回答
慕雪6442864
TA貢獻1812條經驗 獲得超5個贊
通過在您的輔助方法中添加以下行，可以達到預期的結果。
if(target == 0 ) {
Collections.sort(temp); // This will sort your list, that you want to add
if(!res.contains(temp)) // Check if sorted list already existing in your result list or not. Only add the temp list if it does not exist in your res list.
res.add(new ArrayList<>(temp));
return;
}
或者您也可以在列表中按排序順序添加元素res，然后使用 HashSet 從res列表中刪除重復項。
Set<List<Integer>> set = new HashSet<>(res);
res.clear();
res.addAll(set);
吃雞游戲
TA貢獻1829條經驗 獲得超7個贊
完全避免重復（無需顯式檢查）的一種可能的替代方法如下：
與其遍歷輔助函數中 for 循環中的每個元素（請注意，索引參數在遞歸調用中始終相同），不如考慮如下解決方案：
您要么考慮給定索引處的元素，然后使用相同的索引再次遞歸（因此能夠多次考慮相同的元素）或
你不考慮當前元素，用index+1遞歸。
這樣你就不會在你的解決方案中得到重復項。
不在這里發布整個解決方案（不想讓你失去所有的樂趣 :P ），但輔助函數中的遞歸步驟基本上是：
# don't consider element at index, and increment index in recursive call
self.helper(candidates, target, index+1, res, temp)
# consider element at index `index`
self.helper(candidates, target-candidates[index], index, res, temp+[candidates[index]])
牧羊人nacy
TA貢獻1862條經驗 獲得超7個贊
我不確定最好的意思是什么，但你可以使用Collection.sort和Set
public static Set<List<Integer>> combinationSum(int[] candidates, int target)
{
--->>? ? Set<List<Integer>> res = new HashSet<>();
? ? Arrays.sort(candidates);
? ? helper(candidates, target, res, new ArrayList<>(), 0);
? ? return res;
}
private static void helper(int[] candidates, int target, Set<List<Integer>> res, List<Integer> temp, int index) {
? ? if( target < 0) return;
? ? if(target == 0) {
? ? ? ? ArrayList<Integer> newRes = new ArrayList<>(temp);
--->>? ? ? ? Collections.sort(newRes);
? ? ? ? res.add(newRes);
? ? ? ? return;
? ? }
? ? for(int i = index; i < candidates.length; i++) {
? ? ? ? if(candidates[i] > target) {
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? temp.add(candidates[i]);
? ? ? ? helper(candidates, target - candidates[i], res, temp, index);
? ? ? ? temp.remove(temp.size() - 1);
? ? }
}
輸入
候選人 = [2,3,6,7]，目標 = 7
輸出
[[2, 2, 3], [7]]
弒天下
TA貢獻1818條經驗 獲得超8個贊
你不一定需要為此設置。您可以使用然后檢查所有索引是否相等來對兩個數組進行排序Arrays.sort()，例如：
public Boolean isEqual(int[] a1, int[] a2) {
if (a1.length != a2.length) {
return false;
}
Arrays.sort(a1);
Arrays.sort(a2);
for (int i = 0; i < a1.length; i++) {
if (a1[i] != a2[i]) {
return false;
}
}
return true;
}
將此應用于您的結果并保留返回的數組結果false。
添加回答
舉報
0/150
提交
取消