求符合给定条件的整数集

• 求符合给定条件的整数集
• • 题目描述
  • 解题思路
  • AC代码

给定不超过6的正整数A，考虑从A开始的连续4个数字。请输出所有由它们组成的无重复数字的3位数。

题目地址 https://pintia.cn/problem-sets/14/problems/796

第一种思路是三重循环，然后判断相邻循环用的数字不能相等。

第二种思路是把问题泛化为排列问题：从 n 个数字中任取 k (k<=n) 个进行排列。

优劣比较： 当题目中要求的循环数量很多时，手写多重循环是不合适的。排列的实现是基于递归，也可以改成基于 stack 的方式。本质是 DFS 搜索。

// tags: 搜索
// 具体来说是排列
// https://pintia.cn/problem-sets/14/problems/796

#include 
#include 
#include 
#include 

/// @brief 从 N 个数字（可以有重复）中取 K 个进行排列
/// @param a 存储了N个数字的数组。用来从里面抽取任意K个数字进行排列。
/// @param N 数组a的元素数量
/// @param K 需要从数组中选择的元素数量，应当满足 1<=K<=N
/// @param level 当前已经选择了多少个数字。用户调用时通常传0
/// @param result 用来存储结果，长度为K的数组
/// @param visit 用来标记每a数组中的每个元素是否被访问过，长度等于N，元素值为0或1
/// @param cnt 累计产生了多少个搜索结果。用来辅助打印
void perm(int a[], int N, int K, int level, int* result, int* visit, int* cnt)
{
    if (level>=K)
    {
        for (int j = 0; j < level; j++) {
            printf("%d", result[j]);
        }
        *cnt = *cnt + 1;

        // 每打印6个结果后，换行。可改掉。
        if (*cnt % 6 == 0) {
            printf("n");
        } else {
            printf(" ");
        }
        return;
    }
    for (int i = 0; i < N; i++)
    {
        if (visit[i] == false)
        {
            visit[i] = true;
            result[level++] = a[i];
            perm(a, N, K , level, result, visit, cnt);//在未被使用过的里面再选择一个
            level--;
            visit[i] = false;
        }
    }
}

int main()
{
    int a;
    scanf("%d", &a);

    int data[4];
    for (int i=0; i<4; i++)
    {
        data[i] = a + i;
    }

    int result[3];
    int visit[4] = {0};
    int cnt = 0;
    perm(data, 4, 3, 0, result, visit, &cnt);

    return 0;
}