Lecture_Notes/imperfect_notes/Recursion and Backtracking/3.md

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]

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

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 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, '')