【問題描述】[中等]

【解答思路】

1. 減法

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; import java.util.List;public class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {int len = candidates.length;List<List<Integer>> res = new ArrayList<>();if (len == 0) {return res;}// 關鍵步驟Arrays.sort(candidates);Deque<Integer> path = new ArrayDeque<>(len);dfs(candidates, len, 0, target, path, res);return res;}/*** @param candidates 候選數組* @param len 冗余變量* @param begin 從候選數組的 begin 位置開始搜索* @param target 表示剩余，這個值一開始等于 target，基于題目中說明的"所有數字（包括目標數）都是正整數"這個條件* @param path 從根結點到葉子結點的路徑* @param res*/private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {if (target == 0) {res.add(new ArrayList<>(path));return;}for (int i = begin; i < len; i++) {// 大剪枝if (target - candidates[i] < 0) {break;}// 小剪枝if (i > begin && candidates[i] == candidates[i - 1]) {continue;}path.addLast(candidates[i]);// 因為元素不可以重復使用，這里遞歸傳遞下去的是 i + 1 而不是 idfs(candidates, len, i + 1, target - candidates[i], path, res);path.removeLast();}}public static void main(String[] args) {int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};int target = 8;Solution solution = new Solution();List<List<Integer>> res = solution.combinationSum2(candidates, target);System.out.println("輸出 => " + res);} }

2. 加法

class Solution {public List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {int len = candidates.length;boolean[] used = new boolean[len];Arrays.sort(candidates);dfs(candidates,target,new ArrayDeque<Integer>(),0,0);return res;}public void dfs(int[] cand,int target,Deque<Integer> temp,int sum,int index){if(sum>target) return;if(sum==target){res.add(new ArrayList<>(temp));return;}for(int i=index;i<cand.length;++i){if (i > index && cand[i] == cand[i - 1]) {continue;}temp.addLast(cand[i]);dfs(cand,target,temp,sum+cand[i],i+1);temp.removeLast();}} }

【總結】

1. 剪枝說明

2.回溯算法相關題目

[Leedcode][JAVA][第46題][全排列][回溯算法]
[Leetcode][第81題][JAVA][N皇后問題][回溯算法]
[Leetcode][第60題][JAVA][第k個排列][回溯][DFS][剪枝]
[Leetcode][第39題][JAVA][組合總和][回溯][dfs][剪枝]

轉載鏈接：https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/

總結

以上是生活随笔為你收集整理的[Leetcode][第40题][JAVA][数组总和2][回溯][剪枝]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。