[LintCode] k Sum II [Backtracking]

tabalt 發(fā)布于2019-08-14 15:31 / 666人閱讀

摘要：當(dāng)?shù)拇笮闀r(shí)，若也正好減小為，說明當(dāng)前路徑是正確的結(jié)果之一存入新的數(shù)組，再將放入。在循環(huán)遞歸之后，將中最后一個(gè)放入的元素刪除，以在當(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.

Example

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

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

Note

這道題不能用k Sum的做法，因?yàn)橐祷氐氖墙Y(jié)果的集合，而不是數(shù)目或者最優(yōu)解。
我們使用回溯算法，建立helper函數(shù)。從curIndex開始循環(huán)，將循環(huán)到的值A[i]加入curList，然后基于這個(gè)curList繼續(xù)遞歸，不過要調(diào)整target和curIndex。target減小A[i]，curIndex增加1位。當(dāng)curList的大小為k時(shí)，若target也正好減小為0，說明當(dāng)前路徑curList是正確的結(jié)果之一：存入新的數(shù)組temp，再將temp放入res。在循環(huán)遞歸之后，將curList中最后一個(gè)放入的元素刪除，以在當(dāng)前循環(huán)內(nèi)繼續(xù)替換和遞歸。
復(fù)雜度為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);
        }
    }
}