蓝桥杯-粘木棍

import java.util.Scanner;

public class Main {
	static int min_sub;  // 最小的差距

	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		
		int[] mg;
		int[] mg_flag ;
		int[] D_length  ;
		
		min_sub = 700000;
		
		
		int M , N ; //  N 木棍   M  几段
		Scanner sc= new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		mg = new int[N];
		mg_flag = new int[N];
		D_length = new int[M];
		
		for (int i = 0; i < mg.length; i++) {
			mg[i] = sc.nextInt();
		}
		
		dfs(N,mg,mg_flag,D_length);
		
		System.out.println(min_sub);
		
	}
	
	
	static void dfs(int dd,int[] mg,
			int[] mg_flag,int[] D_length
			) {
		
		if(dd == 0) {
			// 分完了 检测当前的 最大插差值
			
		    if(min_sub>=getNowChazhi(D_length)) {
					min_sub = getNowChazhi(D_length);
					return ;
		}
			
			
		}
		
		// 开始分了
		
		for (int i = 0; i < mg.length ; i++) {
                 // 首先要分的棍子必须是没被分过的
			  if(mg_flag[i]==0){
				  //  都给谁呢？  0 - M -1
				  for (int j = 0; j < D_length.length; j++) {
					  mg_flag[i]=1;  // 用过了
					  D_length[j] += mg[i];
					  dfs(dd-1,mg,mg_flag,D_length);
					  D_length[j] -= mg[i];
					  mg_flag[i]=0; 
					  // 回溯
				  }
            	  
            	  
              }			
		}
		
		
	}
	
	static int getNowChazhi(int[] D_length) {
		
		int max = 0;
		int min = 70000000;
		
		for (int i = 0; i < D_length.length; i++) {
			if(max<D_length[i]) max = D_length[i];
			if(min>D_length[i]) min = D_length[i];
		}
		return  Math.abs(max-min);
	}

}