赞
踩
题目链接
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
思路:
index
需要注意class Solution { List<List<Integer>> res = new ArrayList<List<Integer>>(); LinkedList<Integer> p = new LinkedList<>(); int sum = 0; public List<List<Integer>> combinationSum(int[] candidates, int target) { if (candidates.length == 0) return res; backtracking(candidates, target, 0); return res; } public void backtracking(int[] candidates, int target, int index) { if (sum >= target) { if (sum == target) res.add(new ArrayList<>(p)); return; } for (int i = index; i < candidates.length; ++i) { sum += candidates[i]; p.add(candidates[i]); backtracking(candidates, target, i); sum -= candidates[i]; p.removeLast(); } } }
题目链接
是一个类似去重的题目,数组中有重复元素,但每个元素只能取1次,要求sum == target
思路:
[1, 1, 2]
, target = 3
, output = [1, 2]
,只有1个唯一答案used[]
数组,可以用于在for循环
中判断,当前是树枝(深度)搜索还是树层(广度)搜索class Solution { List<List<Integer>> res = new ArrayList<List<Integer>>(); LinkedList<Integer> path = new LinkedList<>(); int sum = 0; public List<List<Integer>> combinationSum2(int[] candidates, int target) { if (candidates.length == 0) return null; boolean[] flag = new boolean[candidates.length]; Arrays.sort(candidates); //排序 backtracking(candidates, target, 0, flag); return res; } public void backtracking(int[] candidates, int target, int index, boolean[] flag) { if (sum >= target) { if (sum == target) res.add(new ArrayList<>(path)); return; } for (int i = index; i < candidates.length; ++i) { if (i != 0 && candidates[i] == candidates[i - 1] && !flag[i - 1]) continue; sum += candidates[i]; path.add(candidates[i]); flag[i] = true; backtracking(candidates, target, i + 1, flag); sum -= candidates[i]; flag[i] = false; path.removeLast(); } } }
思路:
a
之后,在剩余的bcdef
中去选取/切割第二段[startIndex, i]
是否是回文的
class Solution { List<List<String>> res = new ArrayList<List<String>>(); LinkedList<String> path = new LinkedList<>(); public List<List<String>> partition(String s) { if (s.length() == 0) return null; backtreacking(s, 0); return res; } private void backtreacking(String s, int index) { if (index >= s.length()) { res.add(new ArrayList<>(path)); return; } for (int i = index; i < s.length(); ++i) { if (isPalindrome(s, index, i)) { String t = s.substring(index, i + 1); //substring取[i, j) path.add(t); } else continue; backtreacking(s, i + 1); path.removeLast(); } } private boolean isPalindrome(String s, int begin, int end) { int p = begin, q = end; while (p < q) { if (s.charAt(p++) != s.charAt(q--)) return false; } return true; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。