Problem

An array is squareful if the sum of every pair of adjacent elements is a perfect square.

Given an integer array nums, return the number of permutations ofnums that aresquareful.

Two permutations perm1 and perm2 are different if there is some index i such that perm1[i] != perm2[i].

Examples

Example 1

1
2
3

Input: nums = [1,17,8]
Output: 2
Explanation: [1,8,17] and [17,8,1] are the valid permutations.

Example 2

1
2

Input: nums = [2,2,2]
Output: 1

Constraints

  • 1 <= nums.length <= 12
  • 0 <= nums[i] <= 10^9

Solution

Method 1 – Backtracking with Pruning

Intuition

We need to count all unique permutations of the array where every adjacent pair sums to a perfect square. Since the array can have duplicates, we must avoid counting duplicate permutations. We use backtracking to generate all valid permutations, skipping duplicates and pruning paths early if the current pair does not sum to a perfect square.

Approach

  1. Sort the array to handle duplicates easily.
  2. Use a backtracking function that tries to build the permutation step by step:
    • Keep a used array to track which elements are already in the current permutation.
    • For each unused element, if it is the same as the previous and the previous was not used, skip it (to avoid duplicates).
    • If the current element can be appended (either it’s the first, or the sum with the previous is a perfect square), proceed.
    • If the permutation is complete, increment the answer.
  3. Use a helper function to check if a number is a perfect square.
  4. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
class Solution {
public:
    int numSquarefulPerms(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 0;
        vector<bool> used(n, false);
        function<void(vector<int>&, int)> dfs = [&](vector<int>& path, int depth) {
            if (depth == n) { ++ans; return; }
            for (int i = 0; i < n; ++i) {
                if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue;
                if (depth == 0 || isSquare(path.back() + nums[i])) {
                    used[i] = true;
                    path.push_back(nums[i]);
                    dfs(path, depth+1);
                    path.pop_back();
                    used[i] = false;
                }
            }
        };
        auto isSquare = [](int x) {
            int r = sqrt(x);
            return r*r == x;
        };
        vector<int> path;
        dfs(path, 0);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import (
    "sort"
    "math"
)
func numSquarefulPerms(nums []int) int {
    sort.Ints(nums)
    n, ans := len(nums), 0
    used := make([]bool, n)
    var isSquare = func(x int) bool {
        r := int(math.Sqrt(float64(x)))
        return r*r == x
    }
    var dfs func(path []int, depth int)
    dfs = func(path []int, depth int) {
        if depth == n {
            ans++
            return
        }
        for i := 0; i < n; i++ {
            if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
                continue
            }
            if depth == 0 || isSquare(path[len(path)-1]+nums[i]) {
                used[i] = true
                dfs(append(path, nums[i]), depth+1)
                used[i] = false
            }
        }
    }
    dfs([]int{}, 0)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import java.util.*;
class Solution {
    public int numSquarefulPerms(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ans[] = new int[1];
        boolean[] used = new boolean[n];
        backtrack(nums, new ArrayList<>(), used, ans);
        return ans[0];
    }
    void backtrack(int[] nums, List<Integer> path, boolean[] used, int[] ans) {
        if (path.size() == nums.length) { ans[0]++; return; }
        for (int i = 0; i < nums.length; ++i) {
            if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue;
            if (path.isEmpty() || isSquare(path.get(path.size()-1) + nums[i])) {
                used[i] = true;
                path.add(nums[i]);
                backtrack(nums, path, used, ans);
                path.remove(path.size()-1);
                used[i] = false;
            }
        }
    }
    boolean isSquare(int x) {
        int r = (int)Math.sqrt(x);
        return r*r == x;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun numSquarefulPerms(nums: IntArray): Int {
        nums.sort()
        val n = nums.size
        var ans = 0
        val used = BooleanArray(n)
        fun isSquare(x: Int) = kotlin.math.sqrt(x.toDouble()).toInt().let { it*it == x }
        fun dfs(path: MutableList<Int>, depth: Int) {
            if (depth == n) { ans++; return }
            for (i in 0 until n) {
                if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue
                if (depth == 0 || isSquare(path.last() + nums[i])) {
                    used[i] = true
                    path.add(nums[i])
                    dfs(path, depth+1)
                    path.removeAt(path.size-1)
                    used[i] = false
                }
            }
        }
        dfs(mutableListOf(), 0)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def numSquarefulPerms(self, nums: list[int]) -> int:
        from math import isqrt
        nums.sort()
        n = len(nums)
        used = [False]*n
        ans = 0
        def is_square(x):
            r = isqrt(x)
            return r*r == x
        def dfs(path, depth):
            nonlocal ans
            if depth == n:
                ans += 1
                return
            for i in range(n):
                if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]):
                    continue
                if depth == 0 or is_square(path[-1] + nums[i]):
                    used[i] = True
                    dfs(path + [nums[i]], depth+1)
                    used[i] = False
        dfs([], 0)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

impl Solution {
    pub fn num_squareful_perms(mut nums: Vec<i32>) -> i32 {
        fn is_square(x: i32) -> bool {
            let r = (x as f64).sqrt() as i32;
            r*r == x
        }
        fn dfs(nums: &Vec<i32>, used: &mut Vec<bool>, path: &mut Vec<i32>, ans: &mut i32) {
            let n = nums.len();
            if path.len() == n {
                *ans += 1;
                return;
            }
            for i in 0..n {
                if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) { continue; }
                if path.is_empty() || is_square(path[path.len()-1] + nums[i]) {
                    used[i] = true;
                    path.push(nums[i]);
                    dfs(nums, used, path, ans);
                    path.pop();
                    used[i] = false;
                }
            }
        }
        nums.sort();
        let n = nums.len();
        let mut used = vec![false; n];
        let mut path = vec![];
        let mut ans = 0;
        dfs(&nums, &mut used, &mut path, &mut ans);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    numSquarefulPerms(nums: number[]): number {
        nums.sort((a,b)=>a-b);
        const n = nums.length;
        let ans = 0;
        const used = Array(n).fill(false);
        function isSquare(x: number): boolean {
            const r = Math.floor(Math.sqrt(x));
            return r*r === x;
        }
        function dfs(path: number[], depth: number) {
            if (depth === n) { ans++; return; }
            for (let i = 0; i < n; ++i) {
                if (used[i] || (i > 0 && nums[i] === nums[i-1] && !used[i-1])) continue;
                if (depth === 0 || isSquare(path[path.length-1] + nums[i])) {
                    used[i] = true;
                    dfs([...path, nums[i]], depth+1);
                    used[i] = false;
                }
            }
        }
        dfs([], 0);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n! * n), where n is the length of nums. We try all permutations, pruning invalid ones early. The actual number is less due to pruning and duplicate skipping.
  • 🧺 Space complexity: O(n), for recursion stack and auxiliary arrays.