所谓子集和就是在一个数组中找出它的子集，使得该子集的和等于某个固定值。
一般我们都是使用递归加回溯的方式来处理的，代码如下(此处我们只找出一组满足的条件即可)
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;
}
while(step < A.length) {
list.add(A[step]);
if (getSum(list) == m) {
if (getSum(res) == 0) {
res.addAll(list);
}
}
step++;
getSubSet(A, m, step);
list.remove(list.size() - 1); //回溯执行语句，删除列表最后一个元素
}
}
public static void main(String[] args) {
SubSet test = new SubSet();
int[] A = new int[6];
for(int i = 0;i < 6;i++) {
A[i] = i + 1;
}
test.getSubSet(A, 8, 0);
System.out.println(test.getRes());
}
}
运行结果
[1, 2, 5]
但是这个算法的时间复杂度非常高，是NP级别的。如果数据量比较大的时候，将很难完成运算。
现在我们用栈和哈希缓存来加速这个算法。主要是缓存计算结果，不用每次都去getSum中把list的和算一遍。其思想主要是记忆化搜索，可以参考本人这篇博客动态规划、回溯、贪心，分治
public class SubSet {
private List<Integer> list = new ArrayList<>(); //用于存放求取子集中的元素
@Getter
private List<Integer> res = new ArrayList<>();
private Deque<Integer> deque = new ArrayDeque<>();
private Map<String,Integer> map = new HashMap<>();
//求取数组列表中元素和
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;
}
while(step < A.length) {
list.add(A[step]);
if (!map.containsKey(deque.toString())) {
int sum = getSum(list);
deque.push(A[step]);
map.put(deque.toString(),sum);
if (sum == m) {
if (getSum(res) == 0) {
res.addAll(list);
}
}
}else {
int sum = map.get(deque.toString()) + A[step];
deque.push(A[step]);
map.put(deque.toString(),sum);
if (sum == m) {
if (getSum(res) == 0) {
res.addAll(list);
}
}
}
step++;
getSubSet(A, m, step);
list.remove(list.size() - 1); //回溯执行语句，删除列表最后一个元素
deque.pop();
}
}
public static void main(String[] args) {
SubSet test = new SubSet();
int[] A = new int[6];
for(int i = 0;i < 6;i++) {
A[i] = i + 1;
}
test.getSubSet(A, 8, 0);
System.out.println(test.getRes());
}
}
运算结果
[1, 2, 5]
但C#无法满足获取栈的值，只能获取栈的类型，如果我们用遍历的方式去获取栈的值又回到了以前NP级的时间复杂度，故直接使用数字来做哈希表的键。内容如下
using System;
using System.Collections.Generic;
using System.Collections;
using System.Text.RegularExpressions;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Program
{
private class Oranize
{
public List<decimal> array = new List<decimal>();
public List<decimal> res = new List<decimal>();
public Stack<decimal> stack = new Stack<decimal>();
public Hashtable table = new Hashtable();
public decimal index = 0;
public decimal getSum(List<decimal> list)
{
decimal sum = 0;
for (int i = 0; i < list.Count; i++)
{
sum += list[i];
}
return sum;
}
public String stackValue(Stack<decimal> stack)
{
StringBuilder sb = new StringBuilder();
foreach (decimal s in stack)
{
sb.Append(s.ToString());
}
return sb.ToString();
}
public void org(decimal[] arr,decimal all, int step)
{
if (res.Count > 0)
{
return;
}
while (step < arr.Length)
{
array.Add(arr[step]);
if (!table.ContainsKey(index.ToString()))
{
decimal sum = getSum(array);
stack.Push(index);
table.Add(stack.Peek().ToString(), sum);
if (sum == all)
{
if (getSum(res) == 0)
{
foreach (decimal a in array)
{
res.Add(a);
}
}
}
}
else
{
decimal sum = 0;
if (stack.Count > 0)
{
sum = Convert.ToDecimal(table[stack.Peek().ToString()]) + arr[step];
}
else
{
sum = Convert.ToDecimal(table["0"]) + arr[step];
}
index++;
stack.Push(index);
if (table.ContainsKey(stack.Peek().ToString()))
{
table.Remove(stack.Peek().ToString());
}
table.Add(stack.Peek().ToString(), sum);
if (sum == all)
{
if (getSum(res) == 0)
{
foreach (decimal a in array)
{
res.Add(a);
}
}
}
}
step++;
org(arr, all, step);
array.RemoveAt(array.Count - 1);
stack.Pop();
}
}
}
static void Main(string[] args)
{
decimal[] A = new decimal[6];
for (int i = 0; i < 6; i++)
{
A[i] = i + 1;
}
Oranize oranize = new Oranize();
oranize.org(A, 8, 0);
foreach (decimal r in oranize.res)
{
Console.Write(r + ",");
}
Console.ReadLine();
}
}
}
这里我们可以看到如果使用stackValue来获取栈的各个值的字符串是不可取的，同样会非常慢。
由于C#本身的Hashtable在数据量大的情况下存在溢出风险，所以我们要重写哈希表。重写的哈希表的每个节点由红黑树组成，由于我们并不需要删除哈希表内的元素，所以就不写红黑树和哈希表的删除方法。
private class RedBlackTreeMap
{
private static bool RED = true;
private static bool BLACK = false;
private class Node
{
public String key;
public decimal value;
public Node left;
public Node right;
public bool color;
public Node(String key,decimal value,Node left,Node right,bool color)
{
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.color = color;
}
public Node(String key): this(key, 0, null, null, RED)
{ }
public Node(String key,decimal value): this(key, value, null, null, RED)
{ }
}
private Node root;
private int size;
public ISet<String> keySet = new HashSet<String>();
public RedBlackTreeMap()
{
root = null;
size = 0;
}
private bool isRed(Node node)
{
if (node == null)
{
return BLACK;
}
return node.color;
}
private Node leftRotate(Node node)
{
Node ret = node.right;
Node retLeft = ret.left;
node.right = retLeft;
ret.left = node;
ret.color = node.color;
node.color = RED;
return ret;
}
private Node rightRotate(Node node)
{
Node ret = node.left;
Node retRight = ret.right;
node.left = retRight;
ret.right = node;
ret.color = node.color;
node.color = RED;
return ret;
}
private void flipColors(Node node)
{
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
public void add(String key,decimal value)
{
root = add(root, key, value);
keySet.Add(key);
}
private Node add(Node node,String key,decimal value)
{
if (node == null)
{
size++;
return new Node(key, value);
}
if (key.CompareTo(node.key) < 0)
{
node.left = add(node.left, key, value);
}else if (key.CompareTo(node.key) > 0)
{
node.right = add(node.right, key, value);
}else
{
node.value = value;
}
if (isRed(node.right) && !isRed(node.left))
{
node = leftRotate(node);
}
if (isRed(node.left) && isRed(node.left.left))
{
node = rightRotate(node);
}
if (isRed(node.left) && isRed(node.right))
{
flipColors(node);
}
return node;
}
public bool contains(String key)
{
return getNode(root, key) != null;
}
public decimal get(String key)
{
Node node = getNode(root, key);
return node == null ? 0 : node.value;
}
public void set(String key,decimal value)
{
Node node = getNode(root, key);
if (node == null)
{
throw new ArgumentException(key + "不存在");
}
node.value = value;
}
public int getSize()
{
return size;
}
public bool isEmpty()
{
return size == 0;
}
private Node getNode(Node node,String key)
{
if (node == null)
{
return null;
}
if (key.CompareTo(node.key) == 0)
{
return node;
}else if (key.CompareTo(node.key) < 0)
{
return getNode(node.left, key);
}else
{
return getNode(node.right, key);
}
}
}
private class HashFind
{
private int[] capacity = {53,97,193,389,769,1543,3079,6151,12289,24593,
49157,98317,196613,393241,786433,1572869,3145739,
6291469,12582917,25165843,50331653,100663319,
201326611,402653189,805306457,1610612741};
//容忍度上界
private static int upperTol = 10;
//容忍度下届
private static int lowerTol = 2;
private int capacityIndex = 0;
private RedBlackTreeMap[] tables;
private int M;
private int size;
public HashFind()
{
this.M = capacity[capacityIndex];
this.size = 0;
tables = new RedBlackTreeMap[M];
for (int i = 0; i < M; i++)
{
tables[i] = new RedBlackTreeMap();
}
}
private int hash(String key)
{
return (key.GetHashCode() & 0x7fffffff) % M;
}
public void add(String key,decimal value)
{
RedBlackTreeMap map = tables[hash(key)];
if (map.contains(key))
{
map.add(key, value);
}else
{
map.add(key, value);
size++;
if (size >= upperTol * M && capacityIndex + 1 < capacity.Length)
{
capacityIndex++;
resize(capacity[capacityIndex]);
}
}
}
public bool contains(String key)
{
int index = hash(key);
return tables[index].contains(key);
}
public decimal get(String key)
{
int index = hash(key);
return tables[index].get(key);
}
public void set(String key,decimal value)
{
int index = hash(key);
RedBlackTreeMap map = tables[index];
if(!map.contains(key))
{
throw new ArgumentException(key + "不存在");
}
map.add(key, value);
}
public int getSize()
{
return size;
}
public bool isEmpty()
{
return size == 0;
}
private void resize(int newM)
{
RedBlackTreeMap[] newTables = new RedBlackTreeMap[newM];
for (int i = 0; i < newM; i++)
{
newTables[i] = new RedBlackTreeMap();
}
int oldM = this.M;
this.M = newM;
for (int i = 0; i < oldM; i++)
{
RedBlackTreeMap map = tables[i];
foreach (String key in map.keySet)
{
int index = hash(key);
newTables[index].add(key, map.get(key));
}
}
this.tables = newTables;
}
}
private class Oranize
{
public List<decimal> array = new List<decimal>();
public List<decimal> res = new List<decimal>();
public Stack<decimal> stack = new Stack<decimal>();
public HashFind table = new HashFind();
public decimal index = 0;
public decimal getSum(List<decimal> list)
{
decimal sum = 0;
for (int i = 0; i < list.Count; i++)
{
sum += list[i];
}
return sum;
}
//public String stackValue(Stack<decimal> stack)
//{
// StringBuilder sb = new StringBuilder();
// foreach (decimal s in stack)
// {
// sb.Append(s.ToString());
// }
// return sb.ToString();
//}
public void org(decimal[] arr, decimal all, int step)
{
if (res.Count > 0)
{
return;
}
while (step < arr.Length)
{
array.Add(arr[step]);
if (!table.contains(index.ToString()))
{
decimal sum = getSum(array);
stack.Push(index);
table.add(stack.Peek().ToString(), sum);
if (sum == all)
{
if (getSum(res) == 0)
{
foreach (decimal a in array)
{
res.Add(a);
}
}
}
}
else
{
decimal sum = 0;
if (stack.Count > 0)
{
sum = Convert.ToDecimal(table.get(stack.Peek().ToString())) + arr[step];
}
else
{
sum = Convert.ToDecimal(table.get("0")) + arr[step];
}
index++;
stack.Push(index);
if (!table.contains(stack.Peek().ToString()))
{
table.add(stack.Peek().ToString(), sum);
}
if (sum == all)
{
if (getSum(res) == 0)
{
foreach (decimal a in array)
{
res.Add(a);
}
}
}
}
step++;
org(arr, all, step);
array.RemoveAt(array.Count - 1);
stack.Pop();
}
}
}
虽然该算法进行了加速，但是能否算出，依然在于数组元素的个数所组成的和的组合数，比如有1、2、3、4四个数，则这四个数的和的组合数为1、2、3、4、1+2、1+2+3、1+2+4、1+2+3+4、1+3、1+3+4、1+4、2+3、2+3+4、2+4、3+4总共15个。
我们可以用计算组合数算法来进行验证，该算法也是使用递归加记忆化搜索的方式
public class Combine {
private static Map<String,Long> map= new HashMap<>();
/**
* 计算从m个元素中拿出n个元素的组合数
* @param m
* @param n
* @return
*/
private static long comb(int m,int n){
String key= m+","+n;
if(n == 0)
return 1;
if (n == 1)
return m;
if(n > m / 2)
return comb(m,m-n);
if(n > 1){
if(!map.containsKey(key))
map.put(key, comb(m-1,n-1)+comb(m-1,n));
return map.get(key);
}
return -1;
}
public static void main(String[] args) {
long total = 0;
for (int i = 1 ; i <= 4; i++) {
total += comb(4,i);
}
System.out.println(total);
}
}
运行结果
15
我们现在的主要目的是寻找可计算的节点，我们可以先给出一个比较大的数，比如一个数组中有40个元素
public static void main(String[] args) {
long total = 0;
for (int i = 1 ; i <= 40; i++) {
total += comb(40,i);
}
System.out.println(total);
}
运行结果
1099511627775
由结果可知，40个数的组合数达到了万亿级别，一般我们计算机的计算级数量在亿级别就差不多了，再多的话就比较难算的出来了。当然这里我的个人建议是数组元素数量在28个
public static void main(String[] args) {
long total = 0;
for (int i = 1 ; i <= 28; i++) {
total += comb(28,i);
}
System.out.println(total);
}
运行结果
268435455
这里是2.6亿，最后我们来看一下30的组合数
public static void main(String[] args) {
long total = 0;
for (int i = 1 ; i <= 30; i++) {
total += comb(30,i);
}
System.out.println(total);
}
运行结果
1073741823
运行结果为10亿，所以我们可以看出从28到30，增长的组合数绝对不是一点点。这是一个几何级数的增长。
