题解 | #求和#

/**
* 递归时使用String记录，后续去重有点麻烦，欢迎斧正！
*/
import java.io.*;
import java.util.*;
public class Main{
    static int m;
    // 存放可行解字符串，存在重复解
    static ArrayList<String> strList = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while((str = br.readLine()) != null) {
            String[] ss = str.split(" ");
            int n = Integer.parseInt(ss[0]);
            m = Integer.parseInt(ss[1]);
            boolean[] vis = new boolean[n];
            dfs(vis, 0, "");
  			// 这里开始去重，TreeSet自动排序
            Set<String> set = new TreeSet<>();
            for(int i = 0; i < strList.size(); i++) {
                // 把字符串中的数取出来后转成int[]后，排序（升序），
              	// 再转回所要求格式的字符串加入TreeSet
                String tp = "";;
                String[] ns = strList.get(i).split(" ");
                int[] tarr = new int[ns.length];
                for(int v = 0; v < ns.length; v++) {
                    tarr[v] = Integer.parseInt(ns[v]);
                }
                Arrays.sort(tarr);
                for(int v = 0; v < ns.length; v++) {
                    tp += tarr[v] + " ";
                }
                set.add(tp.trim());
            }
            
            StringBuilder sb = new StringBuilder();
            for(String s : set) {
                sb.append(s).append("\n");
            }
            System.out.print(sb.toString());
        }
    }
    
    static void dfs(boolean[] vis, int sum, String str){
        if(sum == m) strList.add(str.trim());
        else if(sum < m){
  			// 这样会有重复解，如1 2 3与3 2 1，后面会去重
            for(int i = 0; i < vis.length; i++) {
                if(!vis[i]) {
                    vis[i] = true;
                    dfs(vis, sum + i + 1, str + (i + 1) + " ");
                    vis[i] = false;
                }
            }
        }
    }
}