def is_safe(row, col):
    for r in range(row):
        c = board[r]
        if c == col or abs(c-col) == abs(r-row):
            return False
    return True

def backtrack(row):
    if row == n:
        result.append(board[:])
        return

    for col in range(n):
        if is_safe(row, col):
            board[row] = col
            backtrack(row + 1)

backtrack(0)
return result

🔹 Complexity
O(N!)

🔹 Interview Tip
Classic backtracking interview problem.

🚀 57. How do you generate subsets / permutations?

🔹 Subsets
🔹 Backtracking Solution
def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path)

        for i in range(start, len(nums)):
            backtrack(i + 1, path + [nums[i]])

    backtrack(0, [])
    return result

🔹 Permutations
def permutations(nums):
    result = []

    def backtrack(path, remaining):
        if not remaining:
            result.append(path)

        for i in range(len(remaining)):
            backtrack(
                path + [remaining[i]],
                remaining[:i] + remaining[i+1:]
            )

    backtrack([], nums)
    return result

🔹 Interview Tip
Backtracking patterns are extremely important.

🚀 58. How do you solve coin-change / unbounded-knapsack?

🔹 Coin Change Problem
Goal: Minimum coins to form amount

🔹 Dynamic Programming Solution
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(
                dp[i],
                dp[i - coin] + 1
            )

    return dp[amount] if dp[amount] != float('inf') else -1

🔹 Complexity
Time: O(amount × coins) 
Space: O(amount)

🔹 Interview Tip
Very popular DP interview question.

🚀 59. How do you compute Fibonacci efficiently (DP vs matrix exponentiation)?

🔹 DP Solution
def fib(n):
    if n <= 1:
        return n

    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b

    return b

🔹 Complexity
Time: O(n) 
Space: O(1)

🔹 Matrix Exponentiation
Uses matrix power. 
Complexity: O(log n) 
Very efficient for huge numbers.

🔹 Interview Tip
Interviewers may ask optimization beyond DP.

🚀 60. How do you implement longest increasing subsequence (LIS)?

🔹 DP Solution
def lis(nums):
    dp = [1] * len(nums)

    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

🔹 Complexity
Time: O(n²) 
Space: O(n)

🔹 Optimized LIS
Uses: Binary search + Greedy 
Complexity: O(n log n)

🔹 Interview Tip
LIS is one of the most important DP problems.

🔥 Double Tap ❤️ For Part-7