题目：
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码，重量分别是1，3，9，27，81。则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。
本题目要求编程实现：对用户给定的重量，给出砝码组合方案。
输入输出用例
例如：
用户输入：
5
程序输出：
9-3-1
用户输入：
19
程序输出：
27-9+1
数据规模和约定
要求程序输出的组合总是大数在前小数在后。
可以假设用户的输入的数字符合范围1~121。
解题代码：
import java.util.Scanner; public class 五个砝码 { public static void main(String[] args) { int[] arr = {81,27,9,3,1}; Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] jilu = new int[5]; boolean[] b = new boolean[5]; f(n,arr,jilu,b, 0, 0); } // n 是要凑齐的数 // arr是砝码组 // jilu 是记录选中的砝码 // k 是要操作的砝码数 // b 记录加减 public static void f(int n, int[] arr,int[] jilu,boolean[] b,int k,int in) { // 出口 if (n == 0) { for (int i = 0; i < in; i++) { if (b[i]) { if (i == 0) { System.out.print( jilu[i]); continue; } System.out.print( "+" + jilu[i]); }else { System.out.print( "-" + jilu[i]); } } System.out.println(); return; } if (k >= arr.length) { return; } // 使用 + // 尝试 n -= arr[k]; jilu[in] = arr[k]; b[in] = true; f(n, arr, jilu, b, k + 1, in + 1); // 回溯 n += arr[k]; jilu[in] = 0; b[in] = false; // 使用 - // 尝试 n += arr[k]; jilu[in] = arr[k]; f(n, arr, jilu, b, k + 1, in + 1); // 回溯 n -= arr[k]; jilu[in] = 0; // 不使用 f(n, arr, jilu, b, k + 1, in); } }
这个题可以使用递归也可以使用循环，因为只有五层，对速度影响不大。
