学步园

 回溯法是基本算法的一种，可以用于解决大致这样的问题：假设我们有一个N个元素的集合{N}，现在要依据该集合生成M个元素的集合{M}，每一个元素的生成都依据一定的规则CHECK。

用回溯法解决此问题，我们可以划分为三个重要组成部分。
步骤
从第一步开始至第M步，每一步都从{N}中选取一个元素放入结果{M}中。
界定
每次选择一个元素时，我们都要用规则CHECK来界定{N}中的元素谁合适。界定规则的描述将决定算法的效率和性能。
回溯
如果第k步不能找到合适的元素或者需要得到更多的结果，返回到第k-1步，继续选择下一个第k-1步的元素。

让我们来运用以上的描述和C++语言来解决数学排列和组合问题。
问题1：从N个元素中选择M个元素进行排列，列出所有结果。

// permutation.h : List all the permutation subsets of a certian set.
//

#pragma once

#include <iostream>
#include <iomanip>
using namespace std;

// Compute P(N, M). N is the total number, M is the selected number.
template<int N, int M>
class CPermutation
{
private:
    int** m_result; // two-dimension array of [m_nCount][M]
    int m_nCount; // how many results
    int m_nIndex; // 0 - m_nCount - 1

public:
    // List all possible results by nesting
    void Count()
    {
        m_nIndex = 0;
        int result[N], used[N];
        for (int i = 0; i < N; i++)
            used[i] = 0;
        CountRecur(result, used, 0);
    }

    void CountRecur(int result[M], int used[M], int i)
    {
        for (int k = 0; k < N; k++)
        {
            if (used[k])
                continue ;

            result[i] = k;
            used[k] = 1;
            if (i < M - 1)
                CountRecur(result, used, i + 1);
            else
                Add(result);
            used[k] = 0;
        }
    }

    // Save the result
    void Add(int sz[M])
    {
        memcpy(m_result[m_nIndex], sz, M * sizeof(int));
        ++m_nIndex;
    }

    // Count the number of subsets
    // C(N, M) = N! / ((N - M)! * M!)
    static int NumberOfResult()
    {
        if (N <= 0 || M <= 0 || M > N)
            return 0;
        int result = 1;
        for (int i = 0; i < M; i++)
            result *= N - i;
        return result;
    }

    // Print them to the standard output device
    void Print()
    {
        for (int i = 0; i < m_nCount; i++)
        {
            cout << setw(3) << setfill(' ') << i + 1 << ":";
            for (int j = 0; j < M; j++)
                cout << setw(3) << setfill(' ') << m_result[i][j] + 1;
            cout << endl;
        }
    }

    CPermutation()
    {
        // allocate memories for the result
        m_nCount = NumberOfResult();
        m_result = new int*[m_nCount];
        for (int i = 0; i < m_nCount; i++)
            m_result[i] = new int[M];
    }
    ~CPermutation()
    {
        // deallocate memories for the result
        for (int i = 0; i < m_nCount; i++)
            delete[] m_result[i];
        delete[] m_result;
    }
};

问题2：从N个元素中选择M个元素进行组合，列出所有结果。
与排列不同的是，组合不需要对选择出来的M个元素进行排列，不妨假定每一组结果中的M个元素从小到大排列。

// combination.h : list all the subsets of a certian set
//

#pragma once

#include <iostream>
#include <iomanip>
using namespace std;

// List all the M-subsets of the N-set
template<int N, int M>
class CCombination
{
private:
    int** m_result; // two-dimension array of m_nCount * M
    int m_nCount; // how many results of M-length array

public:
    CCombination()
    {
        // allocate memories for the result
        m_nCount = NumberOfResult();
        m_result = new int*[m_nCount];
        for (int i = 0; i < m_nCount; i++)
            m_result[i] = new int[M];
    }
    ~CCombination()
    {
        // deallocate memories for the result
        for (int i = 0; i < m_nCount; i++)
            delete[] m_result[i];
        delete[] m_result;
    }

    // process of counting
    void Count()
    {
        int sz[M];
        int nResultCount = 0;
        CountRecur(sz, 0, 0, nResultCount);
    }

    // Print them to the standard output device
    void Print()
    { 
        using std::cout;
        using std::setw;
        using std::setfill;
        using std::endl;

        for (int i = 0; i < m_nCount; i++)
        {
            cout << setw(3) << setfill(' ') << i + 1 << ":";
            for (int j = 0; j < M; j++)
                cout << setw(3) << setfill(' ') << m_result[i][j] + 1;
            cout << endl;
        }
    }

private:
    // Count the number of subsets
    // C(N, M) = N! / ((N - M)! * M!)
    int NumberOfResult()
    {
        int result = 1;
        for (int i = 0; i < M; i++)
            result *= N - i;
        for (int j = 1; j <= M; j++)
            result /= j;
        return result;
    }

    // Get the current value
    // sz - array of the curr