Backtracking

Given an array `nums` of **unique** integers, return all possible subsets of `nums`. The solution set must **not** contain duplicate subsets. You may return the solution in **any order**. **Example 1:** ```java Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] ``` **Example 2:** ```java Input: nums = [7] Output: [[],[7]] ``` **Constraints:** * `1 <= nums.length <= 10` * `-10 <= nums[i] <= 10` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n * (2^n))</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> It is straightforward that if the array is empty we return an empty array. When we have an array <code>[1]</code> which is of size <code>1</code>, we have two subsets, <code>[[], [1]]</code> as the output. Can you think why the output is so? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can see that one subset includes a number, and another does not. From this, we can conclude that we need to find the subsets that include a number and those that do not. This results in <code>2^n</code> subsets for an array of size <code>n</code> because there are many combinations for including and excluding the array of numbers. Since the elements are unique, duplicate subsets will not be formed if we ensure that we don't pick the element more than once in the current subset. Which algorithm is helpful to generate all subsets, and how would you implement it? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use backtracking to generate all possible subsets. We iterate through the given array with an index <code>i</code> and an initially empty temporary list representing the current subset. We recursively process each index, adding the corresponding element to the current subset and continuing, which results in a subset that includes that element. Alternatively, we skip the element by not adding it to the subset and proceed to the next index, forming a subset without including that element. What can be the base condition to end this recursion? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> When the index <code>i</code> reaches the end of the array, we append a copy of the subset formed in that particular recursive path to the result list and return. All subsets of the given array are generated from these different recursive paths, which represent various combinations of "include" and "not include" steps for the elements of the array. As we are only iterating from left to right in the array, we don't pick an element more than once. </p> </details>

You are given an array of **distinct** integers `nums` and a target integer `target`. Your task is to return a list of all **unique combinations** of `nums` where the chosen numbers sum to `target`. The **same** number may be chosen from `nums` an **unlimited number of times**. Two combinations are the same if the frequency of each of the chosen numbers is the same, otherwise they are different. You may return the combinations in **any order** and the order of the numbers in each combination can be in **any order**. **Example 1:** ```java Input: nums = [2,5,6,9] target = 9 Output: [[2,2,5],[9]] ``` Explanation: 2 + 2 + 5 = 9. We use 2 twice, and 5 once. 9 = 9. We use 9 once. **Example 2:** ```java Input: nums = [3,4,5] target = 16 Output: [[3,3,3,3,4],[3,3,5,5],[4,4,4,4],[3,4,4,5]] ``` **Example 3:** ```java Input: nums = [3] target = 5 Output: [] ``` **Constraints:** * All elements of `nums` are **distinct**. * `1 <= nums.length <= 20` * `2 <= nums[i] <= 30` * `2 <= target <= 30` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(2^(t/m))</code> time and <code>O(t/m)</code> space, where <code>t</code> is the given <code>target</code> and <code>m</code> is the minimum value in the given array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Can you think of this problem in terms of a decision tree, where at each step, we have <code>n</code> decisions, where <code>n</code> is the size of the array? In this decision tree, we can observe that different combinations of paths are formed. Can you think of a base condition to stop extending a path? Maybe you should consider the target value. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use backtracking to recursively traverse these paths and make decisions to choose an element at each step. We maintain a variable <code>sum</code>, which represents the sum of all the elements chosen in the current path. We stop this recursive path if <code>sum == target</code>, and add a copy of the chosen elements to the result. How do you implement it? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We recursively traverse the array starting from index <code>i</code>. At each step, we select an element from <code>i</code> to the end of the array. We extend the recursive path with elements where <code>sum <= target</code> after including that element. This creates multiple recursive paths, and we append the current list to the result whenever the base condition is met. </p> </details>

You are given an array of integers `candidates`, which may contain duplicates, and a target integer `target`. Your task is to return a list of all **unique combinations** of `candidates` where the chosen numbers sum to `target`. Each element from `candidates` may be chosen **at most once** within a combination. The solution set must not contain duplicate combinations. You may return the combinations in **any order** and the order of the numbers in each combination can be in **any order**. **Example 1:** ```java Input: candidates = [9,2,2,4,6,1,5], target = 8 Output: [ [1,2,5], [2,2,4], [2,6] ] ``` **Example 2:** ```java Input: candidates = [1,2,3,4,5], target = 7 Output: [ [1,2,4], [2,5], [3,4] ] ``` **Constraints:** * `1 <= candidates.length <= 100` * `1 <= candidates[i] <= 50` * `1 <= target <= 30` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n * (2^n))</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute-force solution would be to create a <code>hash set</code>, which is used to detect duplicates, to get combinations without duplicates. Can you think of a better way without using a <code>hash set</code>? Maybe you should sort the input array and observe the recursive calls that are responsible for duplicate combinations. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use backtracking to generate all combinations whose sum equals the given target. When the input array contains duplicate elements, it may result in duplicate combinations. To avoid this, we can sort the array. Why does sorting help? Because as we traverse the array from left to right, we form combinations with the current element. By skipping duplicate elements, we ensure that the same combinations are not repeated for identical elements. How can you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We recursively traverse the given array starting at index <code>i</code>, with a variable <code>sum</code> representing the sum of the picked elements. We explore elements from <code>i</code> to the end of the array and extend the recursive path if adding the current element results in <code>sum <= target</code>. When we processed an element, we backtrack and proceed to the next distinct element, skipping any similar elements in the middle to avoid duplicate combinations. </p> </details>

Given an array `nums` of **unique** integers, return all the possible permutations. You may return the answer in **any order**. Give any solution out of multiple solutions **Example 1:** ```java Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ``` **Example 2:** ```java Input: nums = [7] Output: [[7]] ``` **Constraints:** * `1 <= nums.length <= 6` * `-10 <= nums[i] <= 10` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n * n!)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A permutation is the same as the array but with the numbers arranged in a different order. The given array itself is also considered a permutation. This means we should make a decision at each step to take any element from the array that has not been chosen previously. By doing this recursively, we can generate all permutations. How do you implement it? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use backtracking to explore all possible permutation paths. We initialize a temporary list to append the chosen elements and a boolean array of size <code>n</code> (the same size as the input array) to track which elements have been picked so far (<code>true</code> means the element is chosen; otherwise, <code>false</code>). At each step of recursion, we iterate through the entire array, picking elements that have not been chosen previously, and proceed further along that path. Can you think of the base condition to terminate the current recursive path? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We observe that every permutation has the same size as the input array. Therefore, we can append a copy of the list of chosen elements in the current path to the result list if the size of the list equals the size of the input array terminating the current recursive path. </p> </details>

You are given an array `nums` of integers, which may contain duplicates. Return all possible subsets. The solution must **not** contain duplicate subsets. You may return the solution in **any order**. Give any solution out of multiple solutions **Example 1:** ```java Input: nums = [1,2,1] Output: [[],[1],[1,2],[1,1],[1,2,1],[2]] ``` **Example 2:** ```java Input: nums = [7,7] Output: [[],[7], [7,7]] ``` **Constraints:** * `1 <= nums.length <= 11` * `-20 <= nums[i] <= 20` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n * (2^n))</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute-force solution would involve creating a hash set and inserting every subset into it. Then, converting the hash set to a list and returning it. However, this approach would require extra space of <code>O(2^n)</code>. Can you think of a better way? Maybe you should sort the input array and observe which recusive calls are resposible to make duplicate subsets. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use backtracking to generate subsets of an array. If the input contains duplicates, duplicate subsets may be created. To prevent this, we sort the array beforehand. For example, in <code>[1, 1, 2]</code>, sorting allows us to create subsets using the first <code>1</code> and skip the second <code>1</code>, ensuring unique subsets. How can you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We start by sorting the input array. Then, we recursively iterate through the array from left to right, extending recursive paths by including or excluding each element. To avoid duplicate subsets, we skip an element if it is the same as the previous one. Finally, we return the generated subsets as a list. </p> </details>

Given a 2-D grid of characters `board` and a string `word`, return `true` if the word is present in the grid, otherwise return `false`. For the word to be present it must be possible to form it with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word. **Example 1:**  ```java Input: board = [ ["A","B","C","D"], ["S","A","A","T"], ["A","C","A","E"] ], word = "CAT" Output: true ``` **Example 2:**  ```java Input: board = [ ["A","B","C","D"], ["S","A","A","T"], ["A","C","A","E"] ], word = "BAT" Output: false ``` **Constraints:** * `1 <= board.length, board[i].length <= 5` * `1 <= word.length <= 10` * `board` and `word` consists of only lowercase and uppercase English letters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(m * (4^n))</code> time and <code>O(n)</code> space, where <code>m</code> is the number of cells in the given <code>board</code> and <code>n</code> is the size of the given <code>word</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> As we can start at any cell on the board, we can explore all paths from that cell. Can you think of an algorithm to do so? Also, you should consider a way to avoid visiting a cell that has already been visited in the current path. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use a hash set to avoid revisiting a cell in the current path by inserting the <code>(row, col)</code> of the visiting cell into the hash set and exploring all paths (four directions, as we can move to four neighboring cells) from that cell. Can you think of the base condition for this recursive path? Maybe you should consider the board boundaries, and also, we can extend a path if the character at the cell matches the character in the word. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use backtracking, starting from each cell on the board with coordinates <code>(row, col)</code> and index <code>i</code> for the given word. We return false if <code>(row, col)</code> is out of bounds or if <code>board[row][col] != word[i]</code>. When <code>i</code> reaches the end of the word, we return true, indicating a valid path. At each step, we add <code>(row, col)</code> to a hash set to avoid revisiting cells. After exploring the four possible directions, we backtrack and remove <code>(row, col)</code> from the hash set. </p> </details>

Given a string `s`, split `s` into substrings where every substring is a palindrome. Return all possible lists of palindromic substrings. You may return the solution in **any order**.Give any solution out of multiple solutions **Example 1:** ```java Input: s = "aab" Output: [["a","a","b"],["aa","b"]] ``` **Example 2:** ```java Input: s = "a" Output: [["a"]] ``` **Constraints:** * `1 <= s.length <= 20` * `s` contains only lowercase English letters. <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n * (2^n))</code> time and <code>O(n)</code> space, where <code>n</code> is the length of the input string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> For a given string there are <code>2^n</code> possible partitions because at each index we have two decisions: we can either partition and start a new string, or continue without partitioning. Can you think of an algorithm to recursively traverse all combinations? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use backtracking to recursively traverse the string with indices <code>j</code> (start of the current substring) and <code>i</code> (current iterating index). At each step, we either skip partitioning at the current index or, if the substring from <code>j</code> to <code>i</code> is a palindrome, make a partition, update <code>j = i + 1</code>, and start a new substring. The base condition to stop the recursion is when <code>j</code> reaches the end of the string. How do you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We start with <code>j = 0</code>, <code>i = 0</code> and a temporary list which stores the substrings from the partitions. Then we recursively iterate the string with the index <code>i</code>. At each step we apply the <code>2</code> decisions accordingly. At the base condition of the recursive path, we make a copy of the current partition list and add it to the result. </p> </details>

You are given a string `digits` made up of digits from `2` through `9` inclusive. Each digit (not including 1) is mapped to a set of characters as shown below: A digit could represent any one of the characters it maps to. Return all possible letter combinations that `digits` could represent. You may return the answer in **any order**. Give any solution out of multiple solutions  **Example 1:** ```java Input: digits = "34" Output: ["dg","dh","di","eg","eh","ei","fg","fh","fi"] ``` **Example 2:** ```java Input: digits = "" Output: [] ``` **Constraints:** * `0 <= digits.length <= 4` * `2 <= digits[i] <= 9` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n * (4^n))</code> time and <code>O(n)</code> space, where <code>n</code> is the length of the input string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> We can use a hash map to pair all the digits with their corresponding letters. Think of this as a decision tree, where at each step, we have a digit, and we select one of multiple characters to proceed to the next digit in the given string <code>digits</code>. Can you think of an algorithm to generate all combinations of strings? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use backtracking where we select a character and process it, then backtrack to process another character. We recursively iterate on the given string with index <code>i</code>. At each step, we consider the letters from the hash map that correspond to the digit at the <code>i-th</code> index. Can you think of the base condition to stop this recursive path? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We initialize an empty string that represents the choices of the characters throughout the current recursive path. When the index <code>i</code> reaches the end of the string, we add the current string to the result list and return. </p> </details>

The **n-queens** puzzle is the problem of placing `n` queens on an `n x n` chessboard so that no two queens can attack each other. A **queen** in a chessboard can attack horizontally, vertically, and diagonally. Given an integer `n`, return all distinct solutions to the **n-queens puzzle**. Each solution contains a unique board layout where the queen pieces are placed. `'Q'` indicates a queen and `'.'` indicates an empty space. You may return the answer in **any order**. **Example 1:**  ```java Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] ``` Explanation: There are two different solutions to the 4-queens puzzle. **Example 2:** ```java Input: n = 1 Output: [["Q"]] ``` **Constraints:** * `1 <= n <= 8` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n!)</code> time and <code>O(n^2)</code> space, where <code>n</code> is the size of the given square board. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A queen can move in <code>8</code> directions, and no two queens can be in the same row or column. This means we can place one queen per row or column. We iterate column-wise and try to place a queen in each column while ensuring no other queen exists in the same row, left diagonal, or left bottom diagonal. Can you think of a recursive algorithm to find all possible combinations? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use backtracking to traverse through the columns with index <code>c</code> while maintaining a board that represents the current state in the recursive path. We reach the base condition when <code>c == n</code> and we add a copy of the board to the result. How would you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We initialize an empty board and recursively go through each column. For each column, we check each cell to see if we can place a queen there. We use a function to check if the cell is suitable by iterating along the left directions and verifying if the same row, left diagonal, or left bottom diagonal are free. If it is possible, we place the queen on the board, move along the recursive path, and then backtrack by removing the queen to continue to the next cell in the column. </p> </details>