LeetCode 526. 优美的排列Java题目要点用 1 ~ n 构造排列 perm下标从 1 开始要求对每个位置 iperm[i] % i 0 或 i % perm[i] 0返回满足条件的排列数量。方法一回溯 剪枝从位置 1 到 n 依次填数字用一个 used 数组标记数字是否已使用。当前位置 pos 只能放满足整除关系的未使用数字。classSolution{privateintcount0;publicintcountArrangement(intn){boolean[]usednewboolean[n1];backtrack(1,n,used);returncount;}privatevoidbacktrack(intpos,intn,boolean[]used){// 所有位置都填完了说明找到一个合法排列if(posn){count;return;}for(intnum1;numn;num){if(used[num])continue;// 满足优美排列条件if(num%pos0||pos%num0){used[num]true;backtrack(pos1,n,used);used[num]false;}}}}复杂度· 时间复杂度最坏 O(n!)但剪枝后远小于全排列。· 空间复杂度O(n)递归栈和 used 数组。方法二状态压缩 DP用二进制 mask 表示哪些数字已经被使用。dp[mask] 表示使用 mask 中数字填充前 popcount(mask) 个位置的方法数。当前要填的位置pos Integer.bitCount(mask) 1尝试把未使用的数字 num 放到 pos如果满足整除条件则转移。classSolution{publicintcountArrangement(intn){inttotalMask1n;int[]dpnewint[totalMask];dp[0]1;for(intmask0;masktotalMask;mask){if(dp[mask]0)continue;intposInteger.bitCount(mask)1;for(intnum1;numn;num){intbit1(num-1);// 数字 num 还没被使用if((maskbit)0){// 满足优美排列条件if(num%pos0||pos%num0){dp[mask|bit]dp[mask];}}}}returndp[totalMask-1];}}复杂度· 时间复杂度O(n * 2^n)· 空间复杂度O(2^n)示例输入n2输出2解释 排列[1,2]1%102%20合法 排列[2,1]2%101%2!0但2%10合法输入n3输出3推荐· n ≤ 15 时回溯法代码简单、实际运行很快面试中更常写。· 状态压缩 DP 思路更系统适合展示动态规划能力。· 两者都可以通过 LeetCode 526。
