hardBacktrackingPure DSA~35 min
Count Arrangements Where Adjacent Sums Are Perfect Squares
You arrange a set of numeric tiles in a row so that every pair of neighbors sums to a perfect square. Count the distinct valid arrangements (identical tiles are indistinguishable).
Problem
Given an integer array nums, return the number of permutations that are 'squareful': for every pair of adjacent elements, their sum is a perfect square. Permutations that are identical as sequences count once.
Input
An integer array nums.
Output
An integer: the number of distinct squareful permutations.
Constraints
- 1 <= nums.length <= 12
- 0 <= nums[i] <= 10^9
Examples
Example 1
Input
nums = [1,17,8]
Output
2
[1,8,17] and [17,8,1] are squareful (9 and 25 are squares).
Example 2
Input
nums = [2,2,2]
Output
1
[2,2,2] is the only arrangement; 2+2=4 is a square.