力扣

admin管理员组

文章数量:1794759

力扣

一、题目描述

假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：

1、第 i 位的数字能被 i 整除
2、i 能被第 i 位上的数字整除
现在给定一个整数 N，请问可以构造多少个优美的排列？

示例1:

输入: 2
输出: 2
解释: 第 1 个优美的排列是 [1, 2]:第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除第 2 个优美的排列是 [2, 1]:第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除

说明:

1. N 是一个正整数，并且不会超过15。

二、实现思路以及实现代码

class Solution {int count  = 0;public int countArrangement(int N) {if(N<=2){return N; }/**回溯法*/boolean[] visited = new boolean[N+1];//判断数字是否被使用过backTrack(1,N,visited);return count;}private void backTrack(int index, int N, boolean[] visited){if(index == N+1){//表示前N位已经凑好count++;}for(int i = 1; i<N+1; i++){if(!visited[i] && (index % i  ==0 || i% index == 0)){//满足条件visited[i] = true;// 标记为遍历过backTrack(index+1,N,visited);//寻找第index+1个满足要求的元素visited[i] = false;//回溯}}}
}

本文标签： 力扣