使用栈的记忆化搜索来加速子集和算法
所谓子集和就是在一个数组中找出它的子集,使得该子集的和等于某个固定值。 一般我们都是使用递归加回溯的方式来处理的,代码如下(此处我们只找出一组满足的条件即可) public class SubSet { private List<Integer> list = new ArrayList<>(); //用于存放求取子集中的元素 @Getter private List<Integer> res = new ArrayList<>(); //求取数组列表中元素和 public int getSum(List<Integer> list) { int sum = 0; for(int i = 0;i < list.size();i++) sum += list.get(i); return sum; } public void getSubSet(int[] A, int m, int step) { if (res.size() > 0) { return; } whil...
