wordpress数据库连接错误,长春seo关键字排名优化,华为云速建站,公司网站对比那几点优势39. 组合总和
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
解题思路#xff1a;candidate的元素个数为n,从n的n次方中选出可能的组合#xff0c;大于目标则抛弃该组合#xff0c;进行回溯
java#xff1a;
class Solu…39. 组合总和
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
解题思路candidate的元素个数为n,从n的n次方中选出可能的组合大于目标则抛弃该组合进行回溯
java
class Solution {public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger res new ArrayList();Arrays.sort(candidates); backtracking(res, new ArrayList(), candidates, target, 0, 0);return res;}public void backtracking(ListListInteger res, ListInteger path, int[] candidates, int target, int sum, int idx) {if (sum target) {res.add(new ArrayList(path));return;}for (int i idx; i candidates.length; i) {if (sum candidates[i] target) break;path.add(candidates[i]);backtracking(res, path, candidates, target, sum candidates[i], i);path.remove(path.size() - 1); }}
}
40.组合总和II
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
解题思路先排序然后遍历如果当前结点与上一节点相同则将会出现重复的遍历结果
class Solution {public ListListInteger combinationSum2(int[] candidates, int target) {ListListInteger res new ArrayList();Arrays.sort(candidates); backtracking(res, new ArrayList(), candidates, target, 0, 0);return res;}public void backtracking(ListListInteger res, ListInteger path, int[] candidates, int target, int sum, int idx) {if (sum target) {res.add(new ArrayList(path));return;}for (int i idx; i candidates.length; i) {if (sum candidates[i] target) break;if(iidxcandidates[i]candidates[i-1]) continue;path.add(candidates[i]);backtracking(res, path, candidates, target, sum candidates[i], i1);path.remove(path.size() - 1); }}
}
131.分割回文串
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
java
class Solution {ListListString lists new ArrayList();DequeString deque new LinkedList();public ListListString partition(String s) {backTracking(s, 0);return lists;}private void backTracking(String s, int startIndex) {if (startIndex s.length()) {lists.add(new ArrayList(deque));return;}for (int i startIndex; i s.length(); i) {if (isPalindrome(s, startIndex, i)) {String str s.substring(startIndex, i 1);deque.addLast(str);} else {continue;}backTracking(s, i 1);deque.removeLast();}}private boolean isPalindrome(String s, int startIndex, int end) {for (int i startIndex, j end; i j; i, j--) {if (s.charAt(i) ! s.charAt(j)) {return false;}}return true;}
}
