本文共 1097 字，大约阅读时间需要 3 分钟。

1. 问题描述：

题目：

那么最终派往W星的观察团会有多少种国别的不同组合呢？

2. 思路分析：

① 仔细分析一下题目我们可以知道实际上这个是与之前的m个具有重复球中取出n个球的问题，所以我们可以直接套用之前写过的具有重复性元素的组合问题的求解的代码

② 中间我们可以记录一下其中组合的过程，这样就可以验证答案是否是正确的了

③ 其中还加了一个小小的优化就是之前的for循环的结束条件是i <= goal，但是后来发现i + cur <= goal 就好了因为当取到的数量大于了了目标之后那么接下来进行的试探就没有意义了，所以可以在for循环的限制条件上加上这个，也是相当于提前进行了剪枝。最终的答案为101

3. 代码如下：

import java.util.ArrayList;import java.util.List;public class Main {	static int count = 0;	static List
   
     res = new ArrayList
    
     ();	public static void main(String[] args) {		int arr[] = {4, 2, 2, 1, 1, 3};		dfs(arr, 0, 0, 5, "");		System.out.println(count);	}	private static void dfs(int[] arr, int k, int cur, int goal, String s) {		if(cur == goal){			count++;			System.out.println(s);			return;		}		if(k == arr.length){			return;		}		//优化的一个点是加上了for循环的第二个限制条件我们可以减少不必要的搜索		for(int i = 0; i <= arr[k] && (i + cur) <= goal; i++){			String t = s;			for(int j = 0; j < i; j++){				s += (char) (k + 'A');			}			dfs(arr, k + 1, cur + i, goal, s);            //回溯			s = t;		}	}}