資訊專欄INFORMATION COLUMN
摘要：當(dāng)?shù)拇笮闀r，若也正好減小為，說明當(dāng)前路徑是正確的結(jié)果之一存入新的數(shù)組，再將放入。在循環(huán)遞歸之后，將中最后一個放入的元素刪除，以在當(dāng)前循環(huán)內(nèi)繼續(xù)替換和遞歸。
Problem
Given n unique integers, number k (1<=k<=n) and target.
Find all possible k integers where their sum is target.
ExampleGiven [1,2,3,4], k = 2, target = 5. Return:
[ [1,4], [2,3] ]Note
這道題不能用k Sum的做法，因為要返回的是結(jié)果的集合，而不是數(shù)目或者最優(yōu)解。
我們使用回溯算法，建立helper函數(shù)。從curIndex開始循環(huán)，將循環(huán)到的值A[i]加入curList，然后基于這個curList繼續(xù)遞歸，不過要調(diào)整target和curIndex。target減小A[i]，curIndex增加1位。當(dāng)curList的大小為k時，若target也正好減小為0，說明當(dāng)前路徑curList是正確的結(jié)果之一：存入新的數(shù)組temp，再將temp放入res。在循環(huán)遞歸之后，將curList中最后一個放入的元素刪除，以在當(dāng)前循環(huán)內(nèi)繼續(xù)替換和遞歸。
復(fù)雜度為O(n^k)。
public class Solution {
public ArrayList> kSumII(int[] A, int k, int target) {
ArrayList> res = new ArrayList();
helper(A, k, target, 0, res, new ArrayList());
return res;
}
public void helper(int[] A, int k, int target, int curIndex, ArrayList> res, ArrayList curList) {
if (curList.size() == k) {
if (target == 0) {
ArrayList temp = new ArrayList(curList);
res.add(temp);
}
return;
}
for (int i = curIndex; i < A.length; i++) {
curList.add(A[i]);
helper(A, k, target-A[i], i+1, res, curList);
curList.remove(curList.size()-1);
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65824.html
摘要：復(fù)雜度思路參考的思路，對于，表示在從到的范圍內(nèi)，先手玩家能拿到的最大的硬幣價值。對于狀態(tài)，先手玩家有兩種選擇，要么拿的硬幣，要么拿的硬幣左邊一個的或者右邊一側(cè)的，如果拿左側(cè)的硬幣，如果拿右側(cè)的硬幣，取兩個值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...
Build Post Office Problem Given a 2D grid, each cell is either an house 1 or empty 0 (the number zero, one), find the place to build a post office, the distance that post office to all the house sum i...
摘要：題目要求輸入和，找到所有個不同數(shù)字的組合，這些組合中數(shù)字的和為參考，解答這是一道典型的的題目，通過遞歸的方式記錄嘗試的節(jié)點，如果成功則加入結(jié)果集，如果失敗則返回上一個嘗試的節(jié)點進(jìn)行下一種嘗試。 題目要求 Find all possible combinations of k numbers that add up to a number n, given that only numbe...
摘要：當(dāng)右括號和左括號的剩余量均為時，及為一個最終結(jié)果。而則會在直接原來的對象上進(jìn)行修改，其指針仍然指向原來的對象。因此在遞歸的過程中使用一定要注意，對對象的修改不要相互干擾。 題目要求 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....
摘要：兩個參賽者輪流從左邊依次拿走或個硬幣，直到?jīng)]有硬幣為止。計算兩個人分別拿到的硬幣總價值，價值高的人獲勝。請判定第一個玩家是輸還是贏樣例給定數(shù)組返回給定數(shù)組返回復(fù)雜度思路考慮先手玩家在狀態(tài)，表示在在第的硬幣的時候，這一位玩家能拿到的最高價值。 LintCode Coins in a line II 有 n 個不同價值的硬幣排成一條線。兩個參賽者輪流從左邊依次拿走 1 或 2 個硬幣，直...
閱讀 1243·2021-09-26 09:46
閱讀 1593·2021-09-06 15:00
閱讀 725·2019-08-30 15:52
閱讀 1126·2019-08-29 13:10
閱讀 1288·2019-08-26 13:47
閱讀 1485·2019-08-26 13:35
閱讀 2034·2019-08-23 18:38
閱讀 733·2019-08-23 17:59
