请教一个问题请教一个问题，4到9之间的数字相加，数字可重复，答案为100的所有组合。求算法

Question

比如4到9之间的数字相加，数字可重复，答案为100的所有组合。求算法 

Answer 1

数学语言表示一下：a * 4 + b * 5 + c * 6 + d * 7 + e * 8 + f * 9 = 100，求解集{a, b, c, d, e, f}，其中a (= [0, 25], b (= [0, 20], c (= [0, 16], d (= [0, 14], e (= [0, 12], f (= [0, 11]暴力法：建立6个数组，预设a .. f的所有可能取值，然后一个个组合找。其中可以做一些优化，不过那都是细节

Answer 2

a * 4 + b * 5 + c * 6 + d * 7 + e * 8 + f * 9 = 100
把这些，写6个循环 就脱了 1楼很是聪明！！

Answer 3

最简单可以用递归搜索
class AddUp {
  private static int start;
  private static int end;
  private static int target;  public static void main(String[] args) {
    start = 4;
    end = 9;
    target = 100;    solve(0, start, new int[6]);
  }  public static void solve(int currentTotal, int currentNumber, int[] answer) {
    if (currentNumber > end)
      return;    for (int i = 0; i <= target / currentNumber; i++) {
      int nextTotal = currentTotal + currentNumber * i;
      answer[currentNumber - start] = i;
      if (nextTotal == 100) {
        // we got one, baby!
        output(answer);
        return;
      }
      else if (nextTotal < 100)
        solve(nextTotal, currentNumber + 1, answer);
      else {
        // it's already impossible to find another one, clear the cached array entry
        answer[currentNumber - start] = 0;
        return;
      }
    }    return;
  }  public static void output(int[] answer) {
    StringBuilder sb = new StringBuilder();
    int total = 0;
    for (int i = 0; i < answer.length; i++) {
      if (answer[i] == 0)
        continue;
      sb.append(i + start);      if (answer[i] > 1)
        sb.append(" * ").append(answer[i]);      total += (i + start) * answer[i];
      if (total != target)
        sb.append(" + ");
    }
    System.out.println(sb.toString());
  }
}

Answer 4

 solve(0, start, new int[6]);
改成
solve(0, start, new int[end - start + 1]);

Answer 5

import java.util.LinkedList;
import java.util.List;public class Hello {
    public static void foo(final int start, final int end, List<Integer> elements, final int result) {
        int sum = 0;
        for (int i : elements) {
            sum += i;
        }        if (sum == result) {
            System.out.println(elements);
            return;
        } else if (sum > result) {
            return;
        }        for (int i = start; i <= end; ++i) {
            elements.add(i);
            foo(i, end, elements, result); // i作为start是为了避免重复，例如[4, 7, 9]与[9, 7, 4], [7, 4, 9]等是重复的
            elements.remove(elements.size() - 1);
        }
    }    public static void main(String[] args) {
        List<Integer> elements = new LinkedList<Integer>();
        System.out.println("Sum is 20");
        foo(4, 9, elements, 20);        System.out.println("\n\nSum is 30");
        foo(4, 9, elements, 30);        // System.out.println("\n\nSum is 100");
        // foo(4, 9, elements, 100);
    }
}
Sum is 20
[4, 4, 4, 4, 4]
[4, 4, 4, 8]
[4, 4, 5, 7]
[4, 4, 6, 6]
[4, 5, 5, 6]
[4, 7, 9]
[4, 8, 8]
[5, 5, 5, 5]
[5, 6, 9]
[5, 7, 8]
[6, 6, 8]
[6, 7, 7]
Sum is 30
[4, 4, 4, 4, 4, 4, 6]
[4, 4, 4, 4, 4, 5, 5]
[4, 4, 4, 4, 5, 9]
[4, 4, 4, 4, 6, 8]
[4, 4, 4, 4, 7, 7]
[4, 4, 4, 5, 5, 8]
[4, 4, 4, 5, 6, 7]
[4, 4, 4, 6, 6, 6]
[4, 4, 4, 9, 9]
[4, 4, 5, 5, 5, 7]
[4, 4, 5, 5, 6, 6]
[4, 4, 5, 8, 9]
[4, 4, 6, 7, 9]
[4, 4, 6, 8, 8]
[4, 4, 7, 7, 8]
[4, 5, 5, 5, 5, 6]
[4, 5, 5, 7, 9]
[4, 5, 5, 8, 8]
[4, 5, 6, 6, 9]
[4, 5, 6, 7, 8]
[4, 5, 7, 7, 7]
[4, 6, 6, 6, 8]
[4, 6, 6, 7, 7]
[4, 8, 9, 9]
[5, 5, 5, 5, 5, 5]
[5, 5, 5, 6, 9]
[5, 5, 5, 7, 8]
[5, 5, 6, 6, 8]
[5, 5, 6, 7, 7]
[5, 6, 6, 6, 7]
[5, 7, 9, 9]
[5, 8, 8, 9]
[6, 6, 6, 6, 6]
[6, 6, 9, 9]
[6, 7, 8, 9]
[6, 8, 8, 8]
[7, 7, 7, 9]
[7, 7, 8, 8]

Answer 6

修改了一下细节
package com.tur.demo;import java.util.LinkedList;
import java.util.List;public class Hello {
    public static void foo(final int start, final int end, final int result, List<Integer> elements) {
        if (start > end) { return; }        int sum = 0;
        for (int i : elements) {
            sum += i;
        }        if (sum == result) {
            System.out.println(elements);
            return;
        } else if (sum > result) {
            return;
        }        for (int i = start; i <= end; ++i) {
            elements.add(i);
            foo(i, end, result, elements); // i作为start是为了避免重复，例如[4, 7, 9]与[9, 7, 4], [7, 4, 9]等是重复的
            elements.remove(elements.size() - 1);
        }
    }    public static void main(String[] args) {
        List<Integer> elements = new LinkedList<Integer>();
        System.out.println("Sum is 20");
        foo(4, 9, 20, elements);        System.out.println("\n\nSum is 30");
        foo(4, 9, 30, elements);        // System.out.println("\n\nSum is 100");
        // foo(4, 9, 100, elements);
    }
}

Answer 7

哎呀我真是。。还是有几个地方写了100。。
先更正，再跟楼上的做一下对比
class AddUp {
  private static int start;
  private static int end;
  private static int target;  public static void main(String[] args) {
    start = 4;
    end = 9;
    target = 100;    for (int i = 0; i < 5000; i++)
      solve(0, start, new int[end - start + 1]);    long now = System.nanoTime();
    for (int i = 0; i < 5000; i++)
      solve(0, start, new int[end - start + 1]);
    System.out.println(System.nanoTime() - now);
  }  public static void solve(int currentTotal, int currentNumber, int[] answer) {
    if (currentNumber > end)
      return;    for (int i = 0; i <= target / currentNumber; i++) {
      int nextTotal = currentTotal + currentNumber * i;
      answer[currentNumber - start] = i;
      if (nextTotal == target) {
        // we got one, baby!
        output(answer);
        return;
      }
      else if (nextTotal < target)
        solve(nextTotal, currentNumber + 1, answer);
      else {
        // it's already impossible to find another one, clear the cached array entry
        answer[currentNumber - start] = 0;
        return;
      }
    }    return;
  }  public static void output(int[] answer) {
    StringBuilder sb = new StringBuilder();
    int total = 0;
    for (int i = 0; i < answer.length; i++) {
      if (answer[i] == 0)
        continue;
      sb.append(i + start);      if (answer[i] > 1)
        sb.append(" * ").append(answer[i]);      total += (i + start) * answer[i];
      if (total != target)
        sb.append(" + ");
    }
    System.out.println(sb.toString());
  }
}

Answer 8

这里纯讨论技术，不针对个人，更没有炫耀。首先做了一下性能对比（注释掉了System.out.print）：
//warm up
for (int i = 0; i < 5000; i++)
          solve(0, start, new int[end - start + 1]);    long now = System.nanoTime();
      for (int i = 0; i < 5000; i++)
    solve(0, start, new int[end - start + 1]);
    System.out.println(System.nanoTime() - now);这里输出的值在3988456000附近，就是4秒左右
for (int i = 0; i < 5000; i++) {
      elements.clear();
      foo(4, 9, 100, elements);
    }    long now = System.nanoTime();
    for (int i = 0; i < 5000; i++) {
      elements.clear();
      count = 0;
      foo(4, 9, 100, elements);
    }
    System.out.println(System.nanoTime() - now);
这里输出18715472000左右，大概是18秒我能一眼观察到的导致性能差异的两点：
1. foo函数有一个计算sum的操作，而solve函数则没有
2. foo函数有对ArrayList的操作，性能上不如直接操作int[]然后再做深入调查：
我在solve函数for循环中的else if和else块中加入了计数器，统计得出值为30143；而在foo函数中的计数器则加在了for循环的上面（外部），得出值为63653。如果将计数器放在函数开始时，它们的值均为97106。
这表明solve函数过滤了更多不可能的情况，从而获得了较好的性能。当然这不是绝对的
[2, 9, 50] solve: 52276，foo: 40831
[4, 9, 50] solve: 2112，foo: 2304
[2, 9, 100] solve: 2026084，foo: 3101490
看上去好像是在解集比较大的时候，solve比较占优先睡觉，明天再研究。。

Answer 9

package test;public class Test5 {
public static void main(String[] args) {
for(int a=0;a<=25;a++){
for(int b=0;b<=20;b++){
for(int c=0;c<=16;c++){
for(int d=0;d<=14;d++){
for(int e=0;e<=12;e++){
for(int f=0;f<11;f++){
if(a*4+b*5+c*6+d*7+e*8+f*9==100){
System.out.println(a+"个4  "
+b+"个5  "+
c+"个6  "+d+"个7   "+
e+"个8   "+f+"个9");
}
}
}
}
}
}
}

}
}

Answer 10

Quote: 引用 13 楼 u010673021 的回复:

package test;public class Test5 {
public static void main(String[] args) {
for(int a=0;a<=25;a++){
for(int b=0;b<=20;b++){
for(int c=0;c<=16;c++){
for(int d=0;d<=14;d++){
for(int e=0;e<=12;e++){
for(int f=0;f<11;f++){
if(a*4+b*5+c*6+d*7+e*8+f*9==100){
System.out.println(a+"个4  "
+b+"个5  "+
c+"个6  "+d+"个7   "+
e+"个8   "+f+"个9");
}
}
}
}
}
}
}

}
}
这方法最直接!!