0996:平方数组的数目(1932 分)
目录
题目
如果一个数组的任意两个相邻元素之和都是 完全平方数 ,则该数组称为 平方数组 。
给定一个整数数组 nums
,返回所有属于 平方数组 的 nums
的排列数量。
如果存在某个索引 i
使得 perm1[i] != perm2[i]
,则认为两个排列 perm1
和 perm2
不同。
示例 1:
输入:nums = [1,17,8] 输出:2 解释:[1,8,17] 和 [17,8,1] 是有效的排列。
示例 2:
输入:nums = [2,2,2] 输出:1
提示:
1 <= nums.length <= 12
0 <= nums[i] <= 109
相似问题:
分析
#1
- 典型的状压 dp,令 dfs(st,i) 代表子集 st 且末尾是 nums[i] 的排列数,枚举下一个数即可递归
- 需要去掉重复的排列,可以利用组合数学的知识,对于重复 v 次的数,除以 v 的阶乘即可
|
|
171 ms
#2
- 解决重复排列还有种常用方法:枚举时,在相同的数中只考虑第一个
- 本题中,将 nums 排序,枚举到 nums[i] 时,假如 nums[i-1]=nums[i] 且 i-1 位于子集 st 中,那么 nums[i] 不考虑
解答
|
|
0 ms