1,2,5,10 面额的纸币,考虑顺序情况下组成10元的方法(1, 2, 5, 10 denominations of notes, considering the order, the method of forming 10 yuan)

 1 package com.company;
 2 
 3 //https://time.geekbang.org/column/article/73511
 4 
 5 import org.junit.Test;
 6 
 7 import java.util.ArrayList;
 8 
 9 public class Lesson5_1 {
10 
11     public static long[] rewards = {1, 2, 5, 10};  // 四种面额的纸币
12 
13     /**
14      * @param totalReward-奖赏总金额,result-保存当前的解
15      * @return void
16      * @Description: 使用函数的递归(嵌套)调用,找出所有可能的奖赏组合
17      */
18 
19     public  static int index = 0;
20 
21     public static void get(long totalReward, ArrayList<Long> result) {
22 
23         // 当totalReward = 0时,证明它是满足条件的解,结束嵌套调用,输出解
24         if (totalReward == 0) {
25             System.out.print(index++);
26             System.out.println(result);
27             return;
28         }
29         // 当totalReward < 0时,证明它不是满足条件的解,不输出
30         else if (totalReward < 0) {
31             return;
32         } else {
33             for (int i = 0; i < rewards.length; i++) {
34                 ArrayList<Long> newResult = (ArrayList<Long>) (result.clone());  // 由于有4种情况,需要clone当前的解并传入被调用的函数
35                 newResult.add(rewards[i]);            // 记录当前的选择,解决一点问题
36                 get(totalReward - rewards[i], newResult);    // 剩下的问题,留给嵌套调用去解决
37             }
38         }
39 
40     }
41 
42 
43     @Test
44     public void Test() {
45         int totalReward = 5;
46         Lesson5_1.get(totalReward, new ArrayList<Long>());
47 
48     }
49 
50 
51 }
————————
 1 package com.company;
 2 
 3 //https://time.geekbang.org/column/article/73511
 4 
 5 import org.junit.Test;
 6 
 7 import java.util.ArrayList;
 8 
 9 public class Lesson5_1 {
10 
11     public static long[] rewards = {1, 2, 5, 10};  // 四种面额的纸币
12 
13     /**
14      * @param totalReward-奖赏总金额,result-保存当前的解
15      * @return void
16      * @Description: 使用函数的递归(嵌套)调用,找出所有可能的奖赏组合
17      */
18 
19     public  static int index = 0;
20 
21     public static void get(long totalReward, ArrayList<Long> result) {
22 
23         // 当totalReward = 0时,证明它是满足条件的解,结束嵌套调用,输出解
24         if (totalReward == 0) {
25             System.out.print(index++);
26             System.out.println(result);
27             return;
28         }
29         // 当totalReward < 0时,证明它不是满足条件的解,不输出
30         else if (totalReward < 0) {
31             return;
32         } else {
33             for (int i = 0; i < rewards.length; i++) {
34                 ArrayList<Long> newResult = (ArrayList<Long>) (result.clone());  // 由于有4种情况,需要clone当前的解并传入被调用的函数
35                 newResult.add(rewards[i]);            // 记录当前的选择,解决一点问题
36                 get(totalReward - rewards[i], newResult);    // 剩下的问题,留给嵌套调用去解决
37             }
38         }
39 
40     }
41 
42 
43     @Test
44     public void Test() {
45         int totalReward = 5;
46         Lesson5_1.get(totalReward, new ArrayList<Long>());
47 
48     }
49 
50 
51 }