C++实现排列组合算法

// PailieZuhe.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>

using namespace std;

void Pailie(int start, int end, int *arr, int &cnt)
{
	if (start + 1 == end) {
		for (int i = 0; i < end; i++)
			cout << arr[i] << " ";
		cnt++;
		cout << endl;
	}

	//深度搜索，每个元素在每个位置都会出现一次
	for (int i = start; i != end; i++) {
		swap(arr[start], arr[i]);
		Pailie(start + 1, end, arr, cnt);
		swap(arr[start], arr[i]);
	}
}

//用数组 a 元素为0/1 来表示arr对应位置是否选择
void Zuhe(int n, int m, int idx, int *arr, int *a, int &cnt)
{
	a[idx] = 1;

	int sum = 0;
	for (int i = 0; i <= idx; i++) 
		sum += a[i];
	if (sum == m) {	//选中元素个数等于m
		for (int i = 0; i <= idx; i++) {
			if (a[i])
				cout << arr[i]<<" ";
		}
		cout << endl;
		cnt++;
	}

	if(idx+1<n)
		Zuhe(n, m, idx+1, arr, a, cnt);

	a[idx] = 0;
	if (idx + 1 < n)
		Zuhe(n, m, idx + 1, arr, a, cnt);
}

int main()
{
	int n,m,val,cnt;

	if (getchar() == 'p') {	//排列
		while (cin>>n) {
			int *arr = new int[n];

			for (int i = 0; i != n; i++) {
				cin >> val;
				arr[i] = val;
			}

			cnt = 0;
			Pailie(0, n, arr, cnt);
			cout << cnt << endl;

			delete[]arr;
		}

	} else {	//组合
		while (cin>>n>>m) {
			int *arr = new int[n];

			for (int i = 0; i != n; i++) {
				cin >> val;
				arr[i] = val;
			}

			cnt = 0;
			int *a = new int[n];
			memset(a, 0, sizeof(int)*n);
			Zuhe(n, m, 0, arr, a, cnt);
			cout << cnt << endl;

			delete[]arr;
			delete[]a;
		}
	}
}