分享回溯法- 找n个数中r个数的组合

1. 问题描述： 找n个数中r个数的组合

2. 问题分析：

   (1) 问题的解空间为一组r元一维向量(a1, a2, a3, ...，ar), 1<=ai<=n, 1<=i<=r用一维数组a存储正在搜索的向量。

   (2) 例子。 以n=5, r=3为例：
    
       5  4  3
       5  4  2
       5  4  1
       5  3  2
       5  3  1
       5  2  1
       4  3  2
       4  3  1
       4  2  1
       3  2  1
      
      分析数据的特点，搜索时依次对数组(一维向量)元素a[1]、a[2]、a[3]进行尝试。
      a[ri]        i1 ~ i2
      a[1]尝试范围 5 ~ 3
      a[2]尝试范围 4 ~ 2
      a[3]尝试范围 3 ~ 1
      且有这样的规律：ri+i1 = n+1; ri+i2 = r+1; 后一个元素至少比前一个数小1
     
      归纳为一般情况：
      a[1]尝试的范围为(n ~ r)
      a[2]尝试的范围为(n-1 ~ r-1)
      ...
      a[r]尝试的范围为(n-r+1, 1)

      由此，搜索约束条件为ri+a[ri]>=r+1; 若ri+a[ri]<r+1，就要回溯到元素a[ri-1]搜索;特别地当a[r]=1时，回溯到a[r-1]。

3. Java代码：

package boke;

/**
 * 回溯算法：找n个数中r个数的组合
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.24
 * 
 */
public class NumbserCombo {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// 测试例子
		NumbserCombo nc = new NumbserCombo(5, 3, 20);
		nc.comb();

	}

	private int n; // 输入数据n
	private int r; // 输入数据r
	private int[] a; // 解向量

	public NumbserCombo(int _n, int _r, int maxR) {
		n = _n;
		r = _r;
		a = new int[maxR];
	}

	/**
	 * 处理方法
	 */
	public void comb() {
		int i, ri;
		ri = 1;
		a[1] = n;

		while (a[1] >= r) { // a[1]肯定大于等于r的，否则搜到到底了
			if (ri < r) { // 没有搜索到底
				if (ri + a[ri] >= r + 1) { // 是否回溯
					a[ri + 1] = a[ri] - 1;
					ri++;
				} else { // 回溯
					ri--;
					a[ri] = a[ri] - 1;
				}
			} else if (ri == r) {
				for (int j = 1; j <= r; j++) {
					System.out.print(a[j] + " ");
				}
				System.out.println("");

				if (a[ri] == 1) { // 是否回溯
					ri--;
					a[ri] = a[ri] - 1; // 回溯
				} else {
					a[ri] = a[ri] - 1; // 搜索到下一个数
				}
			} else {
				return;
			}
		}
	}

}

 

评论

1 楼 bhjackson 2011-09-18  

学习啦，能否详细介绍下回溯的过程？O(∩_∩)O谢谢