c# - 查找满足某些条件的所有集合( vector )

Question

我正在寻找这个问题的解决方案。我有集合的长度 (n)、集合的总和以及可以是集合中某个元素的最大值 k。

例如，n=5，k=3，sum=10

代码应该返回其中一些集合 [3, 3, 2, 1, 1]； [3,2,2,2,1]

如何在 c、c# 中实用地查找这些集合？

Answer 1

这是我在 Java 中的回答的解决方案:

public class Main {

/**
 * @param args the command line arguments
 */
private static void printVectors(int[] p, int n) {

    for (int i = 0; i < n; i++) {
        System.out.print(p[i] + " ");
    }
    System.out.println();
}
//main function
private static void computeVectors(int[] n, int sum, int k, int k1, int i) {


    if (sum == 0) {

        printVectors(n, n.length);
    } else if (i < n.length) {

        for (int j = k; j >= 0; j--) {

            if (j <= k1) {
                n[i] = j;
                computeVectors(n, sum - j, sum - j, k1, i + 1);
            }
        }
    }
}
public static void main(String[] args) {
    // TODO code application logic here
    computeVectors(new int[5], 10, 3, 3, 0);

}

}

如果n=5，程序的一些输出；总和=10； k=3 为:

3 1 2 2 2

3 1 2 1 3

3 1 1 3 2

3 1 1 2 3

3 1 0 3 3

3 0 3 3 1

3 0 3 2 2

3 0 3 1 3

3 0 2 3 2

3 0 2 2 3

3 0 1 3 3

2 3 3 2 0

2 3 3 1 1

2 3 3 0 2

2 3 2 3 0

正如你所看到的computeVectors是一个递归函数，问题是，这个函数是否可以在没有递归的情况下实现，我尝试了下面的代码，但它不起作用:

private static void computeVectorsNoRecursion(int[] n, int sum, int k, int i) {
    if (sum == 0) {

        printVectors(n, n.length);
    } else if (i < n.length) {
        int j=k;
       // for (int j = k; j >= 0; j--) {

            while (j <= k) {
                if(j>=0)
                {
                n[i]=j;
                i++;
              int temp=sum;
                sum=temp-j;
                k=temp-j;
                j--;
                if(i>=n.length)
                {
                    i=0;
                    printVectors(n, n.length);
                }

            }
        }

      //  }
    }
}