[LintCode] k Sum II [Backtracking]

tabalt 发布于2019-08-14 15:31 / 615人阅读

摘要：当的大小为时，若也正好减小为，说明当前路径是正确的结果之一存入新的数组，再将放入。在循环递归之后，将中最后一个放入的元素删除，以在当前循环内继续替换和递归。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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