//  Copyright 2016 The Sawdust Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

package backtracing;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Thanks a lot to Wen, Jie.
 *
 * Note:
 *   1. Sort in ascending order before search.
 *   2. Next loop will start from current index.
 *   3. When backtracking happen, solution need restore to original status.
 *
 *   To make the loop easy, keep the currency types and solutions number in global variable
 *
 */
public class ChangeMoney {
    private int[] currencys;
    private int solutonsNum;

    public ChangeMoney(int[] currencys) {
        this.currencys = currencys;
    }

    private void selectWithDetail(int remain, int target, List solution) {
        for (int i = remain; i < currencys.length; i++) {
            int v = currencys[i];
            int nextTarget = target - v;
            if (nextTarget == 0) {
                solution.add(currencys[i]);
                solutonsNum++;
                System.out.println(solution.toString());

                solution.remove(solution.size() - 1);
                return;
            }
            if (nextTarget < 0) {
                return;
            }
            solution.add(currencys[i]);
            selectWithDetail(i, nextTarget, solution);
            solution.remove(solution.size() - 1);
        }
    }

    private void select(int from, int target) {
        for (int i = from; i < currencys.length; i++) {
            int v = currencys[i];
            int nextTarget = target - v;
            if (nextTarget == 0) {
                solutonsNum++;
                return;
            }
            if (nextTarget < 0) {
                return;
            }

            select(i, nextTarget);
        }
    }

    public void changeWays(int target, boolean withDetail) {
        Arrays.sort(currencys);
        solutonsNum = 0;

        if (withDetail) {
            List<Integer> solution = new LinkedList<>();
            selectWithDetail(0, target, solution);
        } else {
            select(0, target);
        }

        System.out.println("in total:" + solutonsNum);
    }


    public static void main(String[] args) {
        ChangeMoney cm = new ChangeMoney(new int[]{1, 5, 2});

        cm.changeWays(5, true);
        cm.changeWays(5, false);
    }
}

@@ -737,24 +737,30 @@
 Wen, Jie.%0A *
+ %3Cpre%3E
 %0A * Note:%0A *
@@ -759,16 +759,23 @@
 Note:%0A *
+%0A *    
    1. So
@@ -813,16 +813,20 @@
 arch.%0A *
+    
    2. Ne
@@ -863,19 +863,47 @@
 t index.
-%0A *
+ avoid repeated solution%0A *    
    3. Wh
@@ -973,18 +973,16 @@
 s.%0A *%0A *
-  
  To make
@@ -1061,19 +1061,16 @@
 ariable%0A
- *%0A
  */%0Apubl
@@ -2720,17 +2720,174 @@
 %0A    %7D%0A%0A
+    /**%0A     * %3Cpre%3E%0A     * %5B1, 1, 1, 1, 1, 1, 1%5D%0A     * %5B1, 1, 1, 1, 1, 2%5D%0A     * %5B1, 1, 1, 2, 2%5D%0A     * %5B1, 1, 5%5D%0A     * %5B1, 2, 2, 2%5D%0A     * %5B2, 5%5D%0A     */
 %0A
-
     publ
@@ -3008,17 +3008,17 @@
 ngeWays(
-5
+7
 , true);
@@ -3040,17 +3040,17 @@
 ngeWays(
-5
+7
 , false)

Add cases for ChangeMoney