[LintCode] k Sum II [Backtracking]

tabalt 發布于2019-08-14 15:31 / 661人閱讀

摘要：當的大小為時，若也正好減小為，說明當前路徑是正確的結果之一存入新的數組，再將放入。在循環遞歸之后，將中最后一個放入的元素刪除，以在當前循環內繼續替換和遞歸。

Problem

Given n unique integers, number k (1<=k<=n) and target.

Find all possible k integers where their sum is target.

Example

Given [1,2,3,4], k = 2, target = 5. Return:

[
  [1,4],
  [2,3]
]

Note

這道題不能用k Sum的做法，因為要返回的是結果的集合，而不是數目或者最優解。
我們使用回溯算法，建立helper函數。從curIndex開始循環，將循環到的值A[i]加入curList，然后基于這個curList繼續遞歸，不過要調整target和curIndex。target減小A[i]，curIndex增加1位。當curList的大小為k時，若target也正好減小為0，說明當前路徑curList是正確的結果之一：存入新的數組temp，再將temp放入res。在循環遞歸之后，將curList中最后一個放入的元素刪除，以在當前循環內繼續替換和遞歸。
復雜度為O(n^k)。

Solution

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);
        }
    }
}

云服務器 GPU云服務器 backtracking LintCode LintCode134_LRU sum

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65824.html

LintCode Coins in a line III

摘要：復雜度思路參考的思路，對于，表示在從到的范圍內，先手玩家能拿到的最大的硬幣價值。對于狀態，先手玩家有兩種選擇，要么拿的硬幣，要么拿的硬幣左邊一個的或者右邊一側的，如果拿左側的硬幣，如果拿右側的硬幣，取兩個值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...

focusj 2019-08-14 15:03 評論0 收藏0
[LintCode] Build Post Office I & II

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...

1treeS 2019-08-14 15:50 評論0 收藏0
leetcode216. Combination Sum III

摘要：題目要求輸入和，找到所有個不同數字的組合，這些組合中數字的和為參考，解答這是一道典型的的題目，通過遞歸的方式記錄嘗試的節點，如果成功則加入結果集，如果失敗則返回上一個嘗試的節點進行下一種嘗試。題目要求 Find all possible combinations of k numbers that add up to a number n, given that only numbe...

awokezhou 2019-08-15 10:57 評論0 收藏0
leetcode22. Generate Parentheses

摘要：當右括號和左括號的剩余量均為時，及為一個最終結果。而則會在直接原來的對象上進行修改，其指針仍然指向原來的對象。因此在遞歸的過程中使用一定要注意，對對象的修改不要相互干擾。題目要求 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

騫諱護 2019-08-14 18:35 評論0 收藏0
Lintcode Coins in a line II

摘要：兩個參賽者輪流從左邊依次拿走或個硬幣，直到沒有硬幣為止。計算兩個人分別拿到的硬幣總價值，價值高的人獲勝。請判定第一個玩家是輸還是贏樣例給定數組返回給定數組返回復雜度思路考慮先手玩家在狀態，表示在在第的硬幣的時候，這一位玩家能拿到的最高價值。 LintCode Coins in a line II 有 n 個不同價值的硬幣排成一條線。兩個參賽者輪流從左邊依次拿走 1 或 2 個硬幣，直...

2shou 2019-08-14 15:03 評論0 收藏0