[LintCode] k Sum II [Backtracking]
文章目录
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<ArrayList<Integer>> kSumII(int[] A, int k, int target) {
ArrayList<ArrayList<Integer>> res = new ArrayList();
helper(A, k, target, 0, res, new ArrayList<Integer>());
return res;
}
public void helper(int[] A, int k, int target, int curIndex, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> curList) {
if (curList.size() == k) {
if (target == 0) {
ArrayList<Integer> 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);
}
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论