领扣LintCode算法问题答案-90. k数和 II
目录
90. k数和 II描述样例 1：样例 2：
题解鸣谢
90. k数和 II
描述
给定n个不同的正整数，整数k（1<= k <= n）以及一个目标数字。
在这n个数里面找出K个数，使得这K个数的和等于目标数字，你需要找出所有满足要求的方案。
样例 1：
输入: [1,2,3,4], k = 2, target = 5
输出: [[1,4],[2,3]]
样例 2：
输入: [1,3,4,6], k = 3, target = 8
输出: [[1,3,4]]
题解
public class Solution {
public List
<List
<Integer>> kSumII(int[] A
, int k
, int target
) {
Arrays
.sort(A
);
int[] row
= new int[k
];
List
<List
<Integer>> ret
= new ArrayList<>();
kSumII(A
, k
, target
, 0, row
, ret
);
return ret
;
}
public void kSumII(int[] A
, int k
, int target
, int index
, int[] row
, List
<List
<Integer>> ret
) {
if (index
>= A
.length
) {
return;
}
if (k
== 1) {
if (Arrays
.binarySearch(A
, index
, A
.length
, target
) >= 0) {
row
[k
- 1] = target
;
List
<Integer> temp
= new ArrayList<>();
for (int r
: row
) {
temp
.add(r
);
}
ret
.add(temp
);
}
} else {
for (int i
= index
; i
< A
.length
; i
++) {
int n
= A
[i
];
if (n
< target
) {
row
[k
- 1] = n
;
kSumII(A
, k
- 1, target
- n
, i
+ 1, row
, ret
);
}
}
}
}
}
原题链接点这里
鸣谢
非常感谢你愿意花时间阅读本文章，本人水平有限，如果有什么说的不对的地方，请指正。 欢迎各位留言讨论，希望小伙伴们都能每天进步一点点。
