求数组中和为某个值的所有子数组
求数组中和为某个值的所有子数组，比如数组是
[5,5,10,2,3] 一共有四个子数组的和是 15，比如
[5,10]，
[5,10]，
[10,2,3]，
[5,5,2,3]。用递归实现，怎么打印出这些子数组，是用栈实现吗
2016-08-07 11:14 大连理工 Java
关注
全部评论
猫丫 楼主
楼主 大连理工 Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
public class subArrayOfgivenValue {
public static void main(String[] args) {
int[] candidates = { 5, 5, 10, 2, 3 };
int target = 15;
ArrayList<ArrayList<Integer>> res = combinationSum(candidates, target);
for (ArrayList<Integer> list : res) {
System.out.println(list);
}
}
public static ArrayList<ArrayList<Integer>> combinationSum(int[] num, int target) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
// Arrays.sort(num);
Stack<Integer> stk = new Stack<Integer>();
findCombination(result, 0, target, stk, num);
return result;
}
private static void findCombination(ArrayList<ArrayList<Integer>> result, int
index,int target, Stack<Integer> stk, int[] num) {
if (target == 0) {
result.add(new ArrayList<Integer>(stk));
return;
} else {
for (int i = index; i < num.length; i++) {
if (num[i] > target)
continue;
stk.push(num[i]);
findCombination(result, i + 1, target - num[i], stk, num);
stk.pop();
}
}
}
}
剑指MS
南京大学 Java
public class Solution {
public static void main(String[] args) {
int[] candidates = { 5, 5, 10, 2, 3 };
int target = 15;
List<List<Integer>> res = combinationSum(candidates, target);
for (List<Integer> list : res) {
System.out.println(list);
}
}
public static List<List<Integer>> combinationSum(int[] num, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
Arrays.sort(num);
Stack<Integer> stk = new Stack<Integer>();
findCombination(result, 0, target, stk, num);
return result;
}
private static void findCombination(List<List<Integer>> result, int index,
int target, Stack<Integer> stk, int[] num) {
if (target == 0) {
result.add(new ArrayList<Integer>(stk));
return;
} else {
for (int i = index; i < num.length; i++) {
if (num[i] > target)
return;
stk.push(num[i]);
findCombination(result, i + 1, target - num[i], stk, num);
stk.pop();
}
}
}
}
先对数组排序，然后利用一个栈，递归。
cookShell
广东工业大学 C++
个人觉得01背包解最简单，只是时间复杂度需优化。
public static void MultipleEle(int []source, int sum)
{
List<int> tmp = new List<int>();
MultipleEleCore(source, sum, source.Length - 1, tmp);
}
public static void MultipleEleCore(int []source, int sum, int
index, List<int>ilist)
{
if (source == null || ilist == null || source.Length ==
0)
{
return;
}
if (index < 0)
{
return;
}
if (sum == source[index])
{
//if (ilist.Count == 2)
{
Console.Write(source[index] + " ");
foreach (int item in ilist)
{
Console.Write(item + " ");
}
Console.WriteLine();
}
}
ilist.Insert(0, source[index]);
MultipleEleCore(source, sum - source[index], index - 1,
ilist);
ilist.RemoveAt(0);
MultipleEleCore(source, sum, index - 1, ilist);
}
大菜B
北京演艺专修学院 算法工程师
先将数据按从大到小进行排序，然后使用DFS所有可能
#include<iostream>
using
namespace
std
;
int
a
[
100
]
=
{
4
,
3
,
1
,
2
,
1
,
2
}
;
bool
x
[
100
]
;
//标记第i个元素是否已经使用
int
N
=
6
;
//元素个数
int
t
=
4
;
//目标和
int
sum
;
//当前和
int
cmp
(
const
void
*
a
,
const
void
*
b
)
{
return
*
(
int
*
)
b
-
*
(
int
*
)
a
;
}
void
backtrace
(
int
n
)
{
if
(
sum
>
t
)
//当前和大于t
return
;
if
(
sum
=
=
t
)
//当前和等于t,输出结果
{
for
(
int
j
=
0
;
j
<
n
;
+
+
j
)
{
if
(
x
[
j
]
)
cout
<
<
a
[
j
]
<
<
" "
;
}
cout
<
<
endl
;
return
;
}
if
(
n
=
=
N
)
//超过n层
return
;
for
(
int
i
=
n
;
i
<
N
;
+
+
i
)
{
if
(
x
[
i
]
=
=
false
)
//未使用
{
x
[
i
]
=
true
;
sum
+
=
a
[
i
]
;
backtrace
(
i
+
1
)
;
x
[
i
]
=
false
;
sum
-
=
a
[
i
]
;
while
(
i
<
N
-
1
&
&
a
[
i
]
=
=
a
[
i
+
1
]
)
//跳过相同的
i
+
+
;
}
}
}
int
main
(
)
{
sum
=
0
;
memset
(
x
,
0
,
sizeof
(
x
)
)
;
qsort
(
a
,
N
,
sizeof
(
a
[
0
]
)
,
cmp
)
;
backtrace
(
0
)
;
return
0
;
}
相关推荐
蚂蚁集团开奖43人在聊
