本文主要是介绍Backtracking 隐式图搜索 总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
心得： Permutation 就需要visited数组，subset和combination不需要；
Choose, explore, unChoose
Permutations 思路：用visited来表示是否访问过。for循环每次还是从头开始；
class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> lists = new ArrayList<List<Integer>>();int n = nums.length;List<Integer> list = new ArrayList<Integer>();boolean[] visited = new boolean[n];dfs(nums, list, lists, visited);return lists;}private void dfs(int[] nums, List<Integer> list, List<List<Integer>> lists, boolean[] visited) {if(list.size() == nums.length) {lists.add(new ArrayList<Integer>(list));return;}for(int i = 0; i < nums.length; i++) {if(visited[i]) {continue;}visited[i] = true;list.add(nums[i]);dfs(nums, list, lists, visited);list.remove(list.size() - 1);visited[i] = false;}}
}Permutation II 思路：跟上题一样，注意去重复，重复就是选代表，i > 0 && nums[i] == nums[i-1] && !visited[i-1] 就跳过；112；注意需要排序，因为相同的元素挤在一起，那么选代表才有意义，前后才会相等；
class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> lists = new ArrayList<List<Integer>>();int n = nums.length;List<Integer> list = new ArrayList<Integer>();Arrays.sort(nums); // 别忘记了sort，相同的元素挤在一起，那么选代表才有意义；boolean[] visited = new boolean[n];dfs(nums, list, lists, visited);return lists;}private void dfs(int[] nums, List<Integer> list, List<List<Integer>> lists, boolean[] visited) {if(list.size() == nums.length) {lists.add(new ArrayList<Integer>(list));return;}for(int i = 0; i < nums.length; i++) {if(visited[i]) {continue;}if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {continue;}visited[i] = true;list.add(nums[i]);dfs(nums, list, lists, visited);list.remove(list.size() - 1);visited[i] = false;}}
}Next Permutation (这是数学题，固定算法题，不是backtracking) 思路就是找到最大的一个i，递增A[i] < A[i + 1]，然后找到最大的一个j，which 大于这个A[i]. 然后互换i, j, 然后reverse后面的 i + 1 ~ n - 1 array. 这种固定算法题，没有什么区分度。
Find the largest index k such that nums[i] < nums[i + 1]. If no such index exists, just reverse nums and done.
Find the largest index j > i such that nums[i] < nums[j].
Swap nums[i] and nums[j].
Reverse the sub-array nums[i + 1 ~ n - 1].
class Solution {public void nextPermutation(int[] nums) {int n = nums.length;int i = n - 2;for(; i >= 0; i--) {if(nums[i] < nums[i + 1]) {break;}}if(i < 0) {reverse(nums, 0, n - 1);} else {int j = n - 1;for(; j > i; j--) {if(nums[j] > nums[i]) {break;}}swap(nums, i, j);reverse(nums, i + 1, n - 1);}}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}private void reverse(int[] nums, int start, int end) {while(start <= end) {swap(nums, start, end);start++;end--;}}
}Combinations 思路：bracktracking
class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> lists = new ArrayList<List<Integer>>();if(n <= 0 || k <= 0) {return lists;}List<Integer> list = new ArrayList<Integer>();dfs(n, k, list, lists, 1);return lists;}private void dfs(int n, int k, List<Integer> list, List<List<Integer>> lists, int start) {if(list.size() == k) {lists.add(new ArrayList<Integer>(list));return;}for(int i = start; i <= n; i++) {list.add(i);dfs(n, k, list, lists, i + 1);list.remove(list.size() - 1);}}
}Combination Sum 思路：backtracking
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> lists = new ArrayList<List<Integer>>();if(candidates == null || candidates.length == 0) {return lists;}List<Integer> list = new ArrayList<Integer>();dfs(candidates, list, lists, target, 0, 0);return lists;}private void dfs(int[] candidates, List<Integer> list, List<List<Integer>> lists, int target, int cursum, int start) {if(cursum > target) {return;}if(cursum == target) {lists.add(new ArrayList<Integer>(list));return;}for(int i = start; i < candidates.length; i++) {list.add(candidates[i]);cursum += candidates[i];dfs(candidates, list, lists, target, cursum, i);cursum -= candidates[i];list.remove(list.size() - 1);}}
}Combination Sum II 思路：只能用一次，下次循环从i + 1开始；另外还要去重复，选代表；
class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> lists = new ArrayList<List<Integer>>();if(candidates == null || candidates.length == 0) {return lists;}Arrays.sort(candidates);List<Integer> list = new ArrayList<Integer>();dfs(candidates, list, lists, target, 0, 0);return lists;}private void dfs(int[] candidates, List<Integer> list, List<List<Integer>> lists, int target, int cursum, int start) {if(cursum > target) {return;}if(cursum == target) {lists.add(new ArrayList<Integer>(list));return;}for(int i = start; i < candidates.length; i++) {if(i > start && candidates[i] == candidates[i - 1]) {continue;}list.add(candidates[i]);cursum += candidates[i];dfs(candidates, list, lists, target, cursum, i + 1);cursum -= candidates[i];list.remove(list.size() - 1);}}
}Combination Sum III 思路：backtracking, 注意不能重复使用数字，所以要从i + 1开始；
class Solution {public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> lists = new ArrayList<List<Integer>>();List<Integer> list = new ArrayList<>();dfs(k, n, lists, list, 0, 1);return lists;}private void dfs(int k, int n, List<List<Integer>> lists, List<Integer> list, int cursum,int start) {if(cursum > n || list.size() > k) {return;}if(cursum == n && list.size() == k) {lists.add(new ArrayList<Integer>(list));return;}for(int i = start; i <= 9; i++) {cursum += i;list.add(i);dfs(k, n, lists, list, cursum, i + 1);list.remove(list.size() - 1);cursum -= i;}}
}Combination Sum IV 思路：用backtracking写，time out。正确解法是DP. 我们需要一个一维数组dp，其中dp[i]表示目标数为i的解的个数，然后我们从1遍历到target，对于每一个数i，遍历nums数组，如果i>=x, dp[i] += dp[i - x]。这个也很好理解，比如说对于[1,2,3] 4，这个例子，当我们在计算dp[3]的时候，3可以拆分为1+x，而x即为dp[2]，3也可以拆分为2+x，此时x为dp[1]，3同样可以拆为3+x，此时x为dp[0]，我们把所有的情况加起来就是组成3的所有情况了. 跟coin change一样。
class Solution {public int combinationSum4(int[] nums, int target) {if(nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] dp = new int[target + 1];for(Integer a: nums) {if(a <= target) {dp[a] = 1; }}for(int i = 1; i <= target; i++) {for(Integer a: nums) {if(i - a >= 0) {dp[i] += dp[i - a];}}}return dp[target];}
}Subsets 思路：backtracking
class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> lists = new ArrayList<List<Integer>>();if(nums == null || nums.length == 0) {return lists;}List<Integer> list = new ArrayList<>();dfs(nums, lists, list, 0);return lists;}private void dfs(int[] nums, List<List<Integer>> lists, List<Integer> list, int start) {lists.add(new ArrayList<Integer>(list));for(int i = start; i < nums.length; i++) {list.add(nums[i]);dfs(nums, lists, list, i + 1);list.remove(list.size() - 1);}}
}Subsets II 思路：跟I一样，注意去重复；sort之后，选代表；
class Solution {public List<List<Integer>> subsetsWithDup(int[] nums) {List<List<Integer>> lists = new ArrayList<List<Integer>>();if(nums == null || nums.length == 0) {return lists;}Arrays.sort(nums);List<Integer> list = new ArrayList<Integer>();dfs(nums, list, lists, 0);return lists;}private void dfs(int[] nums, List<Integer> list, List<List<Integer>> lists, int start) {lists.add(new ArrayList<Integer>(list));for(int i = start; i < nums.length; i++) {if(i > start && nums[i] == nums[i - 1]) {continue;}list.add(nums[i]);dfs(nums, list, lists, i + 1);list.remove(list.size() - 1);}}
}Palindrome Permutation 思路：palindrome 最多只有一个奇数对；
class Solution {public boolean canPermutePalindrome(String s) {if(s == null || s.length() == 0) {return false;}int[] count = new int[256];for(int i = 0; i < s.length(); i++) {count[s.charAt(i)]++;}int oddcount = 0;for(int i = 0; i < 256; i++) {if(count[i] % 2 == 1) {oddcount++;}}return oddcount <= 1;}
}Palindrome Permutation II 这题首先利用 Palindrome Permutation I来判断是否能够组成Palindrome，另外就是个backtracking这题比较巧妙的是：奇数的时候，直接把奇数的char放在中间，也就是用stringbuilder append一下；后面只用backtracking 巧妙的是sb的两边前后insert和append即可.
class Solution {public List<String> generatePalindromes(String s) {List<String> list = new ArrayList<>();if(s == null || s.length() == 0) {return list;}int[] count = new int[256];for(int i = 0; i < s.length(); i++) {count[s.charAt(i)]++;}StringBuilder sb = new StringBuilder();int oddcount = 0;for(int i = 0; i < 256; i++) {// 把奇数的char放中间，然后dfs前后append；if(count[i] % 2 == 1) {sb.append((char)(i));oddcount++;}}if(oddcount > 1) {return list;}dfs(count, sb, list, s);return list;}private void dfs(int[] count, StringBuilder sb, List<String> list, String s) {if(sb.length() == s.length()) {list.add(sb.toString());return;}for(int i = 0; i < count.length; i++) {if(count[i] >= 2) {count[i] -= 2;sb.append((char)(i));sb.insert(0, (char)(i));dfs(count, sb, list, s);sb.deleteCharAt(0);sb.deleteCharAt(sb.length() - 1);count[i] += 2;}}}
}Letter Combinations of a Phone Number
class Solution {public List<String> letterCombinations(String digits) {List<String> list = new ArrayList<String>();if(digits == null || digits.length() == 0) {return list;}String[] numbers = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};StringBuilder sb = new StringBuilder();dfs(digits, numbers, list, sb, 0);return list;}private void dfs(String digits, String[] numbers, List<String> list, StringBuilder sb, int i) {if(sb.length() == digits.length()) {list.add(sb.toString());return;}int index = digits.charAt(i) - '0';String number = numbers[index];for(int j = 0; j < number.length(); j++) {sb.append(number.charAt(j));dfs(digits, numbers, list, sb, i + 1);sb.deleteCharAt(sb.length() - 1);}}
}Sudoku Solver 经典的bracktracking，tricky的点在于base case如何return true，这个题是loop完所有的点之后就return true。isSafeBoard的时候，计算subbox，要注意：(x/3)*3, (y/3)*3，可以定位到这个x,y的最左上角。try完了，1~9，如果不行，直接return false，如果走到了两个循环的最后，表明resolve完了，直接return true;
class Solution {public List<List<String>> solveNQueens(int n) {List<List<String>> lists = new ArrayList<List<String>>();char[][] board = new char[n][n];for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {board[i][j] = '.';}}solve(board, lists, 0);return lists;}private void solve(char[][] board, List<List<String>> lists, int column) {if(column == board.length) {buildResult(board, lists);return;}for(int i = 0; i < board.length; i++) {if(isvalid(board, i, column)) {board[i][column] = 'Q';solve(board, lists, column + 1);board[i][column] = '.';}}}private void buildResult(char[][] board, List<List<String>> lists) {List<String> list = new ArrayList<>();for(int i = 0; i < board.length; i++) {StringBuilder sb = new StringBuilder();for(int j = 0; j < board[0].length; j++) {sb.append(board[i][j]);}list.add(sb.toString());}lists.add(list);}private boolean isvalid(char[][] board, int x, int y) {int n = board.length;// check row;for(int j = 0; j < n; j++) {if(j != y && board[x][j] == 'Q') {return false;}}// check col;for(int i = 0; i < n; i++) {if(i != x && board[i][y] == 'Q') {return false;}}// check diagnoalfor(int k = 1; k < n; k++) {if((x - k >= 0 && y - k >= 0 && board[x - k][y - k] == 'Q')|| (x - k >= 0 && y + k < n && board[x - k][y + k] == 'Q')|| (x + k < n && y - k >= 0 && board[x + k][y - k] == 'Q')|| (x + k < n && y + k < n && board[x + k][y + k] == 'Q')) {return false;}}return true;}
}Word Search
class Solution {public boolean exist(char[][] board, String word) {int n = board.length;int m = board[0].length;boolean[][] visited = new boolean[n][m];for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(word.charAt(0) == board[i][j]) {if(dfs(board, word, i, j, 0, visited)) {return true;}}}}return false;}private boolean dfs(char[][] board, String word, int x, int y, int index, boolean[][] visited) {if(index == word.length()) {return true;}if(x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y]) {return false;}boolean find = false;if(word.charAt(index) == board[x][y]) {visited[x][y] = true;find = dfs(board, word, x + 1, y, index + 1, visited)|| dfs(board, word, x - 1, y, index + 1, visited)|| dfs(board, word, x, y + 1, index + 1, visited)|| dfs(board, word, x, y - 1, index + 1, visited);visited[x][y] = false;}return find;}
}Word Search II 思路：其实传递trietree进去，就已经相当于把所有的word全部传进去了，那么对于每个 x,y，那么只需要在这个点展开，搜索所有可能的string就可以了。参数传递不需要用word，只需要用trietree，因为是搜所有可能的word；
Time: ( m * n * 4 * 3 ^ (L - 1) )
Space: 26 * N
class Solution {private class TrieNode {public TrieNode[] children;public boolean isword;public String word;public TrieNode () {this.children = new TrieNode[26];this.isword = false;this.word = null;}}private class Trie {public TrieNode root;public Trie() {this.root = new TrieNode();}public void insert(String word) {TrieNode cur = root;for(int i = 0; i < word.length(); i++) {char c = word.charAt(i);if(cur.children[c - 'a'] == null) {cur.children[c - 'a'] = new TrieNode();}cur = cur.children[c - 'a'];}cur.isword = true;cur.word = word;}}public List<String> findWords(char[][] board, String[] words) {List<String> list = new ArrayList<String>();if(board == null || board.length == 0 || board[0].length == 0) {return list;}Trie trie = new Trie();for(String word: words) {trie.insert(word);}int m = board.length; int n = board[0].length;HashSet<String> set = new HashSet<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {boolean[][] visited = new boolean[m][n];search(board, trie.root, visited, set, i, j);}}return new ArrayList<String>(set);}int[][] dirs = {{0,1},{0,-1},{-1,0},{1,0}};private void search(char[][] board, TrieNode root, boolean[][] visited, HashSet<String> set,int x, int y) {if(x < 0 || x >= board.length || y < 0 || y >= board[0].length || visited[x][y]) {return;}TrieNode cur = root;char c = board[x][y];if(cur.children[c - 'a'] == null) {return;}cur = cur.children[c - 'a'];if(cur.isword) {set.add(cur.word);}visited[x][y] = true;for(int[] dir: dirs) {int nx = x + dir[0];int ny = y + dir[1];search(board, cur, visited, set, nx, ny);}visited[x][y] = false;}
}N-Queens 经典的backtracking，注意board的init和最后的string的构成，最主要的还是check row，col，和diagonal，对角线也要check。注意每行i，我都要试一下，然后对于每一列，我放完一个Q之后，move到下一列，最后check diagonal的时候，四个对角线坐标分别是：(x-i, y-i) (x-i, y+i) (x+i, y-i) (x+i, y+i), 只需判断x-i >=0 x+i<n的情况；
class Solution {public List<List<String>> solveNQueens(int n) {List<List<String>> lists = new ArrayList<List<String>>();char[][] board = new char[n][n];for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {board[i][j] = '.';}}dfs(board, lists, 0);return lists;}private void dfs(char[][] board, List<List<String>> lists, int column) {if(column == board.length) {construct(board, lists);return;}// 对于每一个col，每一个row我都要试探一下；for(int i = 0; i < board[0].length; i++) {if(isvalid(board, i, column)) {board[i][column] = 'Q';dfs(board, lists, column + 1);board[i][column] = '.';}}}private void construct(char[][] board, List<List<String>> lists) {List<String> list = new ArrayList<String>();for(int i = 0; i < board.length; i++) {StringBuilder sb = new StringBuilder();for(int j = 0; j < board[0].length; j++) {sb.append(board[i][j]);}list.add(sb.toString());}lists.add(list);}private boolean isvalid(char[][] board, int x, int y) {if(board[x][y] == 'Q') {return false;}int n = board.length;// check row;for(int j = 0; j < n; j++) {if(j != y && board[x][j] == 'Q') {return false;}}// check col;for(int i = 0; i < n; i++) {if(i != x && board[i][y] == 'Q') {return false;}}// check diagonal;for(int i = 1; i < n; i++) {if((x - i >= 0 && y - i >= 0 && board[x - i][y - i] == 'Q')|| (x + i < n && y + i < n && board[x + i][y + i] == 'Q')|| (x - i >= 0 && y + i < n && board[x - i][y + i] == 'Q')|| (x + i < n && y - i >= 0 && board[x + i][y - i] == 'Q')) {return false;}}return true;}
}Generate Parentheses leftremain, rightremain, 不能leftremain > rightremain;
class Solution {public List<String> generateParenthesis(int n) {List<String> list = new ArrayList<String>();StringBuilder sb = new StringBuilder();dfs(list, sb, n, n);return list;}private void dfs(List<String> list, StringBuilder sb, int leftremain, int rightremain) {if(leftremain > rightremain) {return;}if(leftremain == 0 && rightremain == 0) {list.add(new String(sb.toString()));return;}if(leftremain > 0) {sb.append("(");dfs(list, sb, leftremain - 1, rightremain);sb.deleteCharAt(sb.length() - 1);}if(rightremain > 0) {sb.append(")");dfs(list, sb, leftremain, rightremain - 1);sb.deleteCharAt(sb.length() - 1);}}
}Brace Expansion For example, "{a,b,c}d{e,f}" represents the list ["ade", "adf", "bde", "bdf", "cde", "cdf"].
Return all words that can be formed in this manner, in lexicographical order.
思路：iterative 的写法：这题考查stack，也是非常好的题目；每次处理前面的括号，生成新的string，然后丢到stack里面，继续处理；最后要记得sort一下list，然后输出；
public String[] expand(String S) {List<String> list = new ArrayList<>();Stack<String> stack = new Stack<>();stack.push(S);while(!stack.isEmpty()){String curr = stack.pop();//find first brace pairint l = 0,r=0;while(r<curr.length() && curr.charAt(r)!='}'){if(curr.charAt(r)=='{')l = r;r++;}//case1:r==S.len case2:S.charAt(r)=='}'if(r==curr.length()){list.add(curr);continue;}String before = curr.substring(0,l);String[] options = curr.substring(l+1,r).split(",");String after = curr.substring(r+1);for(String opt : options){stack.push(before+opt+after);}}Collections.sort(list);String[] array = new String[list.size()];return list.toArray(array);}backtracking, 考点就是如何分割字符串，核心就是用index标记走到哪里了，然后把 {}找到，并且切出来split，然后for 循环做backtracking
class Solution {public String[] expand(String S) {List<String> list = new ArrayList<String>();StringBuilder sb = new StringBuilder();dfs(S, list, sb, 0);Collections.sort(list);String[] res = new String[list.size()];return list.toArray(res);}private void dfs(String S, List<String> list, StringBuilder sb, int index) {if(index == S.length()) {list.add(new String(sb.toString()));return;}if(S.charAt(index) == '{') {int r = index;while(index < S.length() && S.charAt(r) != '}') {r++;}String middle = S.substring(index + 1, r);String[] splits = middle.split(",");for(String split: splits) {sb.append(split);dfs(S, list, sb, r + 1); // 注意这里是 r + 1;sb.setLength(sb.length() - split.length());}} else {sb.append(S.charAt(index));dfs(S, list, sb, index + 1);sb.deleteCharAt(sb.length() - 1);}}
}Word Pattern II 思路：用hashmap记录之前匹配的c to string, 然后遇见c了，看有没有匹配过，如果匹配过，那么str是不是以prefix开头；如果没有就进行搜索匹配，尝试所有的可能，另外如果之前匹配过的str不能再用了，跳过；
class Solution {public boolean wordPatternMatch(String pattern, String str) {if(pattern == null && str == null) {return true;}if(pattern == null || str == null) {return false;}HashMap<Character, String> hashmap = new HashMap<>();return dfs(pattern, str, hashmap);}private boolean dfs(String pattern, String str, HashMap<Character, String> hashmap) {if(pattern.isEmpty()) {return str.isEmpty();}char c = pattern.charAt(0);if(hashmap.containsKey(c)) {String match = hashmap.get(c);if(!str.startsWith(match)) {return false;} else {return dfs(pattern.substring(1), str.substring(match.length()), hashmap);}} else {// do not contains;for(int i = 1; i <= str.length(); i++) {String match = str.substring(0, i);// 用过的str，不能再用；if(hashmap.values().contains(match)) {continue;}hashmap.put(c, match);if(dfs(pattern.substring(1), str.substring(match.length()), hashmap)) {return true;}hashmap.remove(c);}}return false;}
}Optimal Account Balancing 思路: 统计出+，-之后，把所有不是0的变量全部收集起来，然后做backtracking，用一个正数去抵消一个负数，然后继续进行，统计全局最小txn，即可；注意的是，dfs expore的时候，是start+1,不是i，因为有正负数，i前面有可能有没有处理完的数，所以只能从start + 1开始；
class Solution {public int minTransfers(int[][] transactions) {if(transactions == null || transactions.length == 0 || transactions[0].length == 0) {return 0;}HashMap<Integer, Integer> countmap = new HashMap<>();for(int[] transaction: transactions) {int a = transaction[0];int b = transaction[1];int money = transaction[2];// a -> b , money;countmap.put(a, countmap.getOrDefault(a, 0) - money);countmap.put(b, countmap.getOrDefault(b, 0) + money);}List<Integer> list = new ArrayList<Integer>();for(Integer value: countmap.values()) {list.add(value);}return dfs(list, 0);}private int dfs(List<Integer> list, int start) {while(start < list.size() && list.get(start) == 0) {start++;}if(start == list.size()) {return 0;}int minvalue = Integer.MAX_VALUE;for(int i = start + 1; i < list.size(); i++) {// back tracking, 就是一个个的试探，只要两个数互为相反数，就try；if(list.get(i) * list.get(start) < 0) {list.set(i, list.get(i) + list.get(start));// 注意这里是start + 1, 不是i, 因为里面有正负号，i前面有可能没处理完；// 所以只能从start + 1开始；minvalue = Math.min(minvalue, 1 + dfs(list, start + 1));list.set(i, list.get(i) - list.get(start));}}return minvalue;}
}24 Games 思路：不要考虑括号的迷惑，就是a,b可以有+-*/任何组合就行了。那么这题就变为了backtracking，每次取两个值，进行计算，compute之后有(a + b, a - b, a * b, a / b, b - a, b / a)，然后隐式图搜索，加入其中一个数继续dfs, 最后计算成1个值的时候跟24判断一下，如果接近就是true，否则就是false；经典backtracking；
class Solution {public boolean judgePoint24(int[] cards) {if(cards == null || cards.length == 0) {return false;}List<Double> list = new ArrayList<Double>();for(int card: cards) {list.add((double) card);}return dfs(list);}private boolean dfs(List<Double> list) {if(list.size() == 1) {// 记住，比较绝对值大小return Math.abs(list.get(0) - 24.0)<= 1e-5;} for(int i = 0; i < list.size(); i++) {for(int j = i + 1; j < list.size(); j++) {List<Double> remain = remove(list, i, j);for(Double calres: getCalculateResult(list.get(i), list.get(j))) {remain.add(calres);if(dfs(remain)) {return true;}remain.remove(remain.size() - 1);}}}return false;}private List<Double> remove(List<Double> list, int i, int j) {List<Double> res = new ArrayList<>();for(int k = 0; k < list.size(); k++) {if(k != i && k != j) {res.add(list.get(k));}}return res;}private List<Double> getCalculateResult(double a, double b) {List<Double> list = new ArrayList<Double>();list.add(a + b);list.add(a - b); list.add(b - a);list.add(a * b);list.add(a / b); list.add(b / a);return list;}
}这篇关于Backtracking 隐式图搜索 总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
