Number of Squareful Arrays
--------------------------
> Given A[N]
> array is squareful if for every pair of adjacent elements, their sum is a perfect square
> Find and return the number of permutations of A that are squareful
>  
Example:
A = [2, 2, 2]
output: 1
A = [1, 17, 8]
output: 2
[1, 8, 17], [17, 8, 1]


```python
def  check(a, b):
    sq = int((a + b) ** 0.5)
    return (sq * sq) == (a + b)

    if  len(A) == 1: # corner case
        return  int(check(A[0], 0))

count = 0
def  permute_distinct(S, i):
    global count
    if i == len(S):
        count += 1

    for j in  range(i, len(S)):
        if S[j] in S[i:j]: # prevent duplicates
            continue

    if i > 0  and (not check(S[j], S[i-1])): # invalid solution - branch and bound
        continue

    S[i], S[j] = S[j], S[i]
    permute_distinct(S, i+1)

    S[i], S[j] = S[j], S[i] # backtrack
    permute_distinct(A, 0)
    return count
```

Gray Code
---------

> Given a non-negative integer N representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

> The gray code is a binary numeral system where two successive values differ in only one bit.

  
G(n+1) can be constructed as:
0 G(n)
1 R(n)

```
Example G(2) to G(3):
0 00
0 01
0 11
0 10
----
1 10
1 11
1 01
1 00
```
```python
def  gray(self, n):
    codes = [0, 1] # length 1
    for i in  range(1, n):
        new_codes = [s | (1 << i) for s in  reversed(codes)]
        codes += new_codes
    return codes
```

N Queens
--------

[NQueens - InterviewBit](https://www.interviewbit.com/problems/nqueens/)
Backtracking
- Place one queen per row
- backtrack if failed

Word Break II
-------------
> Given a string A and a dictionary of words B, add spaces in A to construct a sentence where each word is a valid dictionary word.
```
Input 1:
A = "catsanddog",
B = ["cat", "cats", "and", "sand", "dog"]

Output 1:
["cat sand dog", "cats and dog"]
```python
def  wordBreak(A, B):
    B = set(B)
    sents = []
    def foo(i, start, sent):
        word = A[start:i+1]
        if i == len(A):
            if word in B:
                sents.append((sent + ' ' + word).strip())
        return
    if word in B:
        foo(i+1, i+1, sent + ' ' + word)
        foo(i+1, start, sent)
        foo(0, 0, '')
```