问题:
给定一组数,将其排列
使得相邻两个数的和,正好是一个可被平方的数。
求所有的排列可能个数。
Example 1: Input: [1,17,8] Output: 2 Explanation: [1,8,17] and [17,8,1] are the valid permutations. Example 2: Input: [2,2,2] Output: 1 Note: 1 <= A.length <= 12 0 <= A[i] <= 1e9
解法:Backtracking(回溯算法)
- 状态:到目前为止,排列好的数列。(余下几个数left,当前选择的数x)
- 选择:以当前选择的数 为标准,下一个能与他之和满足条件,成为平方数的,所有可能数。
- ⚠️ 注意:若数列中存在重复的数字,那么当前为止该数字只能选择一次,作为一个排列。
- 递归退出条件:
- left==0,所有数用完,找到一个满足条件的解,res++,return
- 尝试完所有可能,未找到,return
对于本问题:
- 求排列:避免重复元素->使用set:count对不同元素,进行计数。
- 每次递归,用掉一个数,count[x]--
- 递归结束,恢复count[x]++
- 构造每个元素,下一个可选的所有数:使用map:opt:
- key=当前元素x,value={ 可选元素1,可选元素2...... } y
- 这些可选元素满足:sqrt(x+y)^2 = x+y
♻️