硬币找零细则问题
硬币找零：获得找零的各种情况，candidates={3,6,7,9},target=9,输出[[3,3,3],[3,6],[9]]。动态规划只能得到不同情况的总数，不能获得具体结果。
import java.util.*;
public class Main {
List<List<Integer>> results = new ArrayList<>();
Set<String> unique = new HashSet<>();
public static void main(String[] args) {
int[] candidates = {3, 6, 7, 9};
Main m = new Main();
Arrays.sort(candidates);
m.change(candidates, 9, new LinkedList<>());
System.out.println(m.results.size());
}
public void change(int[] candidates, int target, LinkedList<Integer> result) {
if(target == 0){
StringBuilder key = new StringBuilder();
List<Integer> temp = new LinkedList<>(result);
Collections.sort(temp);
for(int i : temp){
key.append(i);
}
if(!unique.contains(key.toString())) {
results.add(temp);
unique.add(key.toString());
}
return;
}
for (int candidate : candidates) {
result.offerLast(candidate);
if (target - candidate >= 0) {
change(candidates, target - candidate, result);
}
result.pollLast();
}
}
}
