T: O(2 ^ n) For every index i two recursive case originates, So Time Complexity is O(2^n). There are 2 ^ n subsets to generate.
S: O(n) The space complexity can be reduced if the output array is not stored and the static and global variable is used to store the output string.
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
dfs(nums, 0, new ArrayList<>(), result);
return result;
}
private void dfs(int[] nums, int startIndex, List<Integer> curt, List<List<Integer>> result) {
result.add(new ArrayList<>(curt));
for (int i = startIndex; i < nums.length; i++) {
curt.add(nums[i]);
dfs(nums, i + 1, curt, result);
curt.remove(curt.size() - 1);
}
}
Sort array and add code below to skip over duplicates:
if (i > currentIndex && nums[i] == nums[i - 1]) {
continue;
}
Typical backtracking template.
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
dfs(0, new ArrayList<>(), res, candidates, target);
return res;
}
private void dfs(int startIndex,
List<Integer> curtList,
List<List<Integer>> result,
int[] candidates,
int target) {
if (target == 0) {
result.add(new ArrayList<>(curtList));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (target - candidates[i] < 0) continue;
curtList.add(candidates[i]);
dfs(i, curtList, result, candidates, target - candidates[i]);
curtList.remove(curtList.size() - 1);
}
}
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
cur = []
candidates.sort
self.helper(candidates,0,cur,res,0,target)
return res
def helper(self, candidates,start_index, cur, res,sum,target):
if sum == target:
res.append(copy.deepcopy(cur))
for i in range(start_index,len(candidates)):
if sum +candidates[i] > target:
continue
Remove duplicate by checking the last element is the same as current element. For example. [1, 1, 5, 6] only output one result [1, 5, 6]. Use if (i > startIndex && candidates[i] == candidates[i - 1]) continue; to remove duplicate.
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
dfs(0, new ArrayList<>(), res, candidates, target);
return res;
}
private void dfs(int startIndex,
List<Integer> curtList,
List<List<Integer>> result,
int[] candidates,
int target) {
if (target == 0) {
result.add(new ArrayList<>(curtList));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (i > startIndex && candidates[i] == candidates[i - 1]) continue;
if (target - candidates[i] < 0) continue;
curtList.add(candidates[i]);
dfs(i + 1, curtList, result, candidates, target - candidates[i]);
curtList.remove(curtList.size() - 1);
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
dfs(new ArrayList<>(), 1, n, k, res);
return res;
}
private void dfs(List<Integer> curt, int start, int n, int k, List<List<Integer>> res) {
if (n == 0 && curt.size() == k) {
res.add(new ArrayList<>(curt));
return;
}
for (int i = start; i <= 9; i++) {
if (n - i < 0 || curt.size() >= k) {
continue;
}
curt.add(i);
dfs(curt, i + 1, n - i, k, res);
curt.remove(curt.size() - 1);
}
}
To get the number of combinations sums to target. DFS Reduce each number on each level, if the target reach 0, it means there is 1 combination. Summarize the combinations of each level and return. Use memo to store sum : count relationship.
public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
return dfs(nums, target, new HashMap<>());
}
private int dfs(int[] nums, int target, Map<Integer, Integer> memo) {
if (memo.containsKey(target)) {
return memo.get(target);
}
if (target == 0) {
return 1;
}
int count = 0;
for (int n : nums) {
if (target - n < 0) {
continue;
}
count += dfs(nums, target - n, memo);
}
memo.put(target, count);
return count;
}
def combinationSum4(self, nums: List[int], target: int) -> int:
dic = {}
return self.dfs(nums, target, dic)
def dfs(self, nums, target, dic):
if target in dic:
return dic[target]
if target == 0:
return 1
count = 0
for n in nums:
if target - n < 0:
continue
count += self.dfs(nums, target - n, dic)
dic[target] = count
return count
Backtracking starting from 0 on each level. Use a boolean array to check if this element has been visited.
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
dfs(nums, new ArrayList<>(), new boolean[nums.length], result);
return result;
}
private void dfs(int[] nums,
List<Integer> curtList,
boolean[] visited,
List<List<Integer>> result) {
if (curtList.size() == nums.length) {
result.add(new ArrayList<>(curtList));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
curtList.add(nums[i]);
dfs(nums, curtList, visited, result);
curtList.remove(curtList.size() - 1);
visited[i] = false;
}
}
def permute(self, nums: List[int]) -> List[List[int]]:
bool_array = [False]*len(nums)
result =[]
self.helper(nums,[], result, bool_array)
return result
def helper(self, nums, curr, result,bool_array):
if curr and len(curr)==len(nums):
result.append(copy.deepcopy(curr))
for i in range(len(nums)):
if bool_array[i]==False:
curr.append(nums[i])
bool_array[i] = True
Sort array. Also remove duplicate when the current element equals previous element, and the previous element is visited ().
if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])) {
continue;
}
public boolean canJump(int[] nums) {
return dfs(nums, 0);
}
private boolean dfs(int[] nums, int index) {
if (index >= nums.length - 1) {
return true;
}
for (int i = 1; i <= nums[index]; i++) {
if (dfs(nums, index + i)) {
return true;
}
}
return false;
}
The array is not sorted. For example, [4, 6, 7, 5, 7], you don't add
[4,6]
[4,6,7]
and [4,6,7]
but need add [4, 6, 7, 7]. It requires to remove duplicate on each layer by use a set.
public List<List<Integer>> findSubsequences(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
dfs(nums, 0, new ArrayList<>(), result);
return result;
}
private void dfs(int[] nums,
int startIndex,
List<Integer> list,
List<List<Integer>> res) {
if (list.size() >= 2) {
res.add(new ArrayList<>(list));
}
Set<Integer> set = new HashSet<>();
for (int i = startIndex; i < nums.length; i++) {
if (set.contains(nums[i])) continue;
if (list.isEmpty() || nums[i] >= list.get(list.size() - 1)) {
set.add(nums[i]);
list.add(nums[i]);
dfs(nums, i + 1, list, res);
list.remove(list.size() - 1);
}
}
}
End the traversal when reach leaf node. Add root.left != null and root.right != null condition to traversal to guarantee no null node is reached.
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
helper(root, sum, new ArrayList<>(), result);
return result;
}
private void helper(TreeNode root,
int sum,
List<Integer> curtList,
List<List<Integer>> res) {
if (root.left == null && root.right == null) {
if (sum == root.val) {
curtList.add(root.val);
res.add(new ArrayList<>(curtList));
curtList.remove(curtList.size() - 1);
}
return;
}
curtList.add(root.val);
if (root.left != null) helper(root.left, sum - root.val, curtList, res);
if (root.right != null) helper(root.right, sum - root.val, curtList, res);
curtList.remove(curtList.size() - 1);
}
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> res = new ArrayList<>();
dfs(res, new ArrayList<Integer>(), n, 2);
return res;
}
public void dfs(List<List<Integer>> res, ArrayList<Integer> temp, int n, int s) {
if (n <= 1) {
if (temp.size() > 1) {
res.add(new ArrayList<Integer>(temp));
}
return;
}
for (int i = s; i <= n; i++) {
if (n % i == 0) {
temp.add(i);
dfs(res, temp, n / i, i);
temp.remove(temp.size()-1);
}
}
}
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> res = new ArrayList<>();
if (n <= 1) return res;
dfs(res, new ArrayList<>(), 2, n);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> curt, int index, int n) {
for (int i = index; i * i <= n; i++) {
if (n % i != 0) continue;
curt.add(i);
curt.add(n / i);
res.add(new ArrayList<>(curt));
curt.remove(curt.size() - 1);
dfs(res, curt, i, n / i);
curt.remove(curt.size() - 1);
}
}
def getFactors(self, n: int) -> List[List[int]]:
res = []
self.dfs(2, n, [], res)
return res
def dfs(self, startindex, n, curt, res):
if n == 1 and len(curt) > 1:
res.append(copy.deepcopy(curt))
return
for i in range(startindex, n + 1):
if n % i == 0:
self.dfs(i, n // i, curt + [i], res)
DFS Backtracking all path.
T: O(2 ^ n)
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
helper(nums, 0, 0, S);
return count;
}
private void helper(int[] nums, int index, int sum, int target) {
if (index == nums.length) {
if (sum == target) count++;
return;
}
helper(nums, index + 1, sum + nums[index], target);
helper(nums, index + 1, sum - nums[index], target);
}
Add memorization. O(n * S)
public int findTargetSumWays(int[] nums, int S) {
int[][] memo = new int[nums.length][2001];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return helper(nums, 0, 0, S, memo);
}
private int helper(int[] nums, int index, int sum, int target, int[][] memo) {
if (index == nums.length) {
return (sum == target) ? 1 : 0;
}
if (memo[index][sum + 1000] != -1) {
return memo[index][sum + 1000];
}
memo[index][sum + 1000] = helper(nums, index + 1, sum + nums[index], target, memo)
+ helper(nums, index + 1, sum - nums[index], target, memo);
return memo[index][sum + 1000];
}
Backtracking to generate parentheses as well as maintain balances of the brackets. Append "(" and left + 1, bal + 1, or append ")" and right + 1, bal - 1.
When bal < 0 it means any invalid solution such as "))((". When bal == 0 and sb.length() == n * 2 it means it is a valid solution.
T: O(2 ^ n) (actually it is 4^n / sqrt(n)) S: 4^n / sqrt(n)
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
if (n == 0) return list;
dfs(n, new StringBuilder(), 0, 0, 0, list);
return list;
}
private void dfs(int n,
StringBuilder sb,
int left,
int right,
int bal, List<String> list) {
if (bal < 0) return;
if (sb.length() == n * 2) {
if (left == right && left == n && bal == 0) {
list.add(sb.toString());
}
return;
}
int len = sb.length();
sb.append('(');
dfs(n, sb, left + 1, right, bal + 1, list);
sb.setLength(len);
sb.append(')');
dfs(n, sb, left, right + 1, bal - 1, list);
sb.setLength(len);
}
def generateParenthesis(self, n: int) -> List[str]:
res = []
self.dfs(0, 0, 0, n, "", res)
return res
def dfs(self, left, right, bal, n, s, res):
if bal < 0:
return
if len(s) == n * 2:
if left == n and right == n and bal == 0:
res.append(s)
return
self.dfs(left + 1, right, bal + 1, n, s + "(", res)
self.dfs(left, right + 1, bal - 1, n, s + ")", res)
Count the number of left brackets and right brackets when need to make a balance. Backtracking to get the string when left == 0 and right == 0 and balance == 0.
public List<String> removeInvalidParentheses(String s) {
Set<String> set = new HashSet<>();
int left = 0, right = 0;
for (char c : s.toCharArray()) {
if (c == '(') left++;
else if (c == ')') {
if (left > 0) left--;
else right++;
}
}
dfs(s.toCharArray(), 0, new StringBuilder(), left, right, 0, set);
return new ArrayList<>(set);
}
private void dfs(char[] chars,
int i,
StringBuilder sb,
int left,
int right,
int bal,
Set<String> set) {
if (left < 0 || right < 0 || bal < 0) return;
if (i == chars.length) {
if (left == 0 && right == 0 && bal == 0) set.add(sb.toString());
return;
}
int len = sb.length();
if (chars[i] == '(') {
dfs(chars, i + 1, sb, left - 1, right, bal, set);
dfs(chars, i + 1, sb.append("("), left, right, bal + 1, set);
} else if (chars[i] == ')') {
dfs(chars, i + 1, sb, left, right - 1, bal, set);
dfs(chars, i + 1, sb.append(")"), left, right, bal - 1, set);
} else {
dfs(chars, i + 1, sb.append(chars[i]), left, right, bal, set);
}
sb.setLength(len);
}
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(0);
dfsSearch(graph, 0, res, path);
return res;
}
private void dfsSearch(int[][] graph, int node, List<List<Integer>> res, List<Integer> path) {
if (node == graph.length - 1) {
res.add(new ArrayList<Integer>(path));
return;
}
for (int nextNode : graph[node]) {
path.add(nextNode);
dfsSearch(graph, nextNode, res, path);
path.remove(path.size() - 1);
}
}
public List<List<Integer>> kSumII(int[] nums, int k, int target) {
// write your code here
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0 || nums.length < k) {
return res;
}
Arrays.sort(nums);
dfs(nums, k, target, 0, new ArrayList<>(), res);
return res;
}
private void dfs(int[] nums,
int k,
int target,
int startIndex,
List<Integer> curt,
List<List<Integer>> res) {
if (target == 0 && curt.size() == k) {
res.add(new ArrayList<>(curt));
}
for (int i = startIndex; i < nums.length; i++) {
if (target - nums[i] < 0 || curt.size() >= k) {
continue;
}
curt.add(nums[i]);
target -= nums[i];
dfs(nums, k, target, i + 1, curt, res);
target += nums[i];
curt.remove(curt.size() - 1);
}
}
T: O(3^n + 4^ m) where N is the number of digits in the input that maps to 3 letters (e.g. 2, 3, 4, 5, 6, 8) and M is the number of digits in the input that maps to 4 letters (e.g. 7, 9), and N+M is the total number digits in the input. S: T: O(3^n + 4^ m)
Map<Integer, List<String>> map = new HashMap<>();
public List<String> letterCombinations(String digits) {
map.put(2, Arrays.asList("a", "b", "c"));
map.put(3, Arrays.asList("d", "e", "f"));
map.put(4, Arrays.asList("g", "h", "i"));
map.put(5, Arrays.asList("j", "k", "l"));
map.put(6, Arrays.asList("m", "n", "o"));
map.put(7, Arrays.asList("p", "q", "r", "s"));
map.put(8, Arrays.asList("t", "u", "v"));
map.put(9, Arrays.asList("w", "x", "y", "z"));
List<String> result = new ArrayList<>();
if (digits == null || digits.isEmpty()) return result;
dfs(digits, 0, new StringBuilder(), result);
return result;
}
private void dfs(String digits, int index, StringBuilder sb, List<String> res) {
if (index == digits.length()) {
res.add(sb.toString());
return;
}
for (String c : map.get(digits.charAt(index) - '0')) {
sb.append(c);
dfs(digits, index + 1, sb, res);
sb.setLength(sb.length() - 1);
}
}
Backtracking until find answer. Be careful with the number of groups found.
public boolean canPartitionKSubsets(int[] nums, int k) {
int n = nums.length;
int sum = 0;
for (int num : nums) sum += num;
if (sum % k != 0) {
return false;
}
return dfs(nums, 0, 0, sum / k, new boolean[n], 0, k);
}
private boolean dfs(int[] nums, int index, int sum, int target, boolean[] used, int useItem, int k) {
if (k == 1) {
return true;
}
if (sum == target && useItem > 0) {
return dfs(nums, 0, 0, target, used, useItem, k - 1);
}
for (int i = index; i < nums.length; i++) {
if (used[i] || sum + nums[i] > target) continue;
used[i] = true;
if (dfs(nums, i + 1, sum + nums[i], target, used, useItem + 1, k)) {
return true;
}
used[i] = false;
}
return false;
}
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
n = len(nums)
sum = 0
for num in nums:
sum += num
if sum % k != 0:
return False
used = [False for i in range(n)]
return self.dfs(nums, 0, 0, int(sum / k), 0, k, used)
def dfs(self, nums, index, curtsum, target, useItems, k, used):
if k == 1:
return True
if curtsum == target and useItems > 0:
return self.dfs(nums, 0, 0, target, useItems, k - 1, used)
for i in range(index, len(nums)):
if used[i] or curtsum + nums[i] > target:
continue
used[i] = True
if self.dfs(nums, i + 1, curtsum + nums[i], target, useItems + 1, k, used):
return True
used[i] = False
return False
Map<String, List<Integer>> map = new HashMap<>();
public List<Integer> diffWaysToCompute(String input) {
if (map.containsKey(input)) return map.get(input);
List<Integer> list = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
if ("+-*".indexOf(input.charAt(i)) != -1) {
String left = input.substring(0, i);
String right = input.substring(i + 1);
List<Integer> leftList = diffWaysToCompute(left);
List<Integer> rightList = diffWaysToCompute(right);
for (int l : leftList) {
for (int r : rightList) {
char c = input.charAt(i);
switch (c) {
case '+' : list.add(l + r);
break;
case '-' : list.add(l - r);
break;
case '*' : list.add(l * r);
break;
}
}
}
}
}
if (list.size() == 0) list.add(Integer.valueOf(input));
map.put(input, list);
return list;
}
Create a map to calculate all balance of each person. Store all non-zero balance to a list to do backtracking.
Start the backtracking from 0 position, set the list.get(pos) as curt value, find the next balance between pos + 1 and array length, check if next and curt are opposite sign (curt * next < 0).
Set the list(i) as curt + next then keep the traversal from pos + 1.
When see list.get(pos) == 0, means it can traverse from pos + 1.
public int minTransfers(int[][] transactions) {
Map<Integer, Integer> balance = new HashMap<>();
for (int[] t : transactions) {
balance.putIfAbsent(t[0], 0);
balance.putIfAbsent(t[1], 0);
balance.put(t[0], balance.get(t[0]) + t[2]);
balance.put(t[1], balance.get(t[1]) - t[2]);
}
List<Integer> list = new ArrayList<>();
for (int key : balance.keySet()) {
if (balance.get(key) != 0) list.add(balance.get(key));
}
return dfs(list, 0);
}
private int dfs(List<Integer> list, int index) {
if (index == list.size()) return 0;
int curt = list.get(index);
if (curt == 0) {
return dfs(list, index + 1);
}
int min = Integer.MAX_VALUE;
for (int i = index + 1; i < list.size(); i++) {
int next = list.get(i);
if (curt * next < 0) {
list.set(i, curt + next);
min = Math.min(min, dfs(list, index + 1) + 1);
list.set(i, next);
}
if (next == -curt) break;
}
return min;
}
Start from row 0, only fill col and cross diag on each spot. When row reach n, output a valid result. The cross diagonal coordinates are calculated by:
int cross1 = row + j;
int cross2 = row - j + n - 1;
int n;
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
this.n = n;
char[][] grid = new char[n][n];
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j++) {
grid[i][j] = '.';
}
}
boolean[] col = new boolean[n];
boolean[] diag = new boolean[2 * n - 1];
boolean[] diag2 = new boolean[2 * n - 1];
dfs(0, col, diag, diag2, grid, res);
return res;
}
private void dfs(int x, boolean[] col, boolean[] diag, boolean[] diag2, char[][] grid, List<List<String>> res) {
if (x == n) {
List<String> toAdd = new ArrayList<>();
for (int i = 0; i < n; i ++) {
toAdd.add(String.valueOf(grid[i]));
}
res.add(toAdd);
return;
}
for (int j = 0; j < n; j++) {
int dval = x - j + n - 1;
int adval = x - (n - 1 - j) + n - 1;
if (col[j] || diag[dval] || diag2[adval]) continue;
col[j] = true;
diag[x + n - j - 1] = true;
diag2[x + j] = true;
grid[x][j] = 'Q';
dfs(x + 1, col, diag, diag2, grid, res);
grid[x][j] = '.';
diag2[x + j] = false;
diag[x + n - j - 1] = false;
col[j] = false;
}
}
Traverse the entire floor and detect if it is visited and movable. The direction is base on the sum of previous direction and the delta. turnRight to the next direction and ndir = (dir + k) % 4 . Also step back after the current dfs is completed.
Robot robot;
Set<Integer> visited = new HashSet<>();
int[][] dirs = new int[][]{{-1,0}, {0,1}, {1,0}, {0,-1}};
public void cleanRoom(Robot robot) {
this.robot = robot;
dfs(0, 0, 0);
}
private void dfs(int x, int y, int dir) {
robot.clean();
visited.add(x * 10000 + y);
for (int k = 0; k < 4; k++) {
int ndir = (dir + k) % 4;
int nx = x + dirs[ndir][0];
int ny = y + dirs[ndir][1];
if (!visited.contains(nx * 10000 + ny) && robot.move()) {
dfs(nx, ny, ndir);
stepBack();
}
robot.turnRight();
}
}
private void stepBack() {
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
}
Cut the pattern and str, backtracking to detect if any pattern would move forward. Use a set to detect the cut has been visited.
public boolean wordPatternMatch(String pattern, String str) {
Map<Character, String> map = new HashMap<>();
return dfs(pattern.toCharArray(), 0, str, 0, map, new HashSet<>());
}
private boolean dfs(char[] arr, int index, String s, int i, Map<Character, String> map, Set<String> set) {
if (index == arr.length && i == s.length()) {
return true;
}
if (index == arr.length || i == s.length()) {
return false;
}
char c = arr[index];
if (map.containsKey(c)) {
String curt = map.get(c);
if (!s.substring(i).startsWith(curt)) return false;
return dfs(arr, index + 1, s, i + curt.length(), map, set);
}
for (int k = i; k < s.length(); k++) {
String cut = s.substring(i, k + 1);
if (set.contains(cut)) continue;
map.put(c, cut);
set.add(cut);
if (dfs(arr, index + 1, s, k + 1, map, set)) {
return true;
}
map.remove(c);
set.remove(cut);
}
return false;
}
Use a StringBuilder to append the digits to crack the safe, also use visited set to keep track of all combinations. Add unique combinations as well as reach the passcode size equals to k^n.
public String crackSafe(int n, int k) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append('0');
int targetSize = (int)Math.pow(k, n);
Set<String> visited = new HashSet<>();
visited.add(sb.toString());
dfs(n, k, sb, visited, targetSize);
return sb.toString();
}
private boolean dfs(int n, int k, StringBuilder sb,
Set<String> visited, int targetSize) {
if (visited.size() == targetSize) return true;
String curt = sb.substring(sb.length() - n + 1);
for (int i = 0; i < k; i++) {
String next = curt + String.valueOf(i);
if (visited.contains(next)) continue;
visited.add(next);
sb.append(i);
if (dfs(n, k, sb, visited, targetSize)) {
return true;
} else {
sb.deleteCharAt(sb.length() - 1);
visited.remove(next);
}
}
return false;
}
This question asks to get all number of patterns from number of keys from m to n. Backtracking to sum up all numbers from starting point 1 to 9, also the remain combinations are between m to n.
Create a skip matrix to determine if the number need to be skipped. For example, between 1 to 3 is 2, it needs skip or visited. Use a boolean array to determine if a number is visited.
public int numberOfPatterns(int m, int n) {
int[][] skip = new int[10][10];
skip[1][3] = skip[3][1] = 2;
skip[1][7] = skip[7][1] = 4;
skip[3][9] = skip[9][3] = 6;
skip[7][9] = skip[9][7] = 8;
skip[1][9] = skip[9][1] = skip[3][7] = skip[7][3]
= skip[2][8] = skip[8][2] = skip[4][6] = skip[6][4] = 5;
boolean[] used = new boolean[10];
int res = 0;
for (int k = m; k <= n; k++) {
for (int start = 1; start <= 9; start++) {
res += dfs(k - 1, used, skip, start);
}
}
return res;
}
private int dfs(int remain, boolean[] used, int[][] skip, int curt) {
if (remain < 0) return 0;
if (remain == 0) return 1;
used[curt] = true;
int res = 0;
for (int next = 1; next <= 9; next++) {
if (!used[next] && (skip[curt][next] == 0 || used[skip[curt][next]])) {
res += dfs(remain - 1, used, skip, next);
}
}
used[curt] = false;
return res;
}
There is a way to eliminate the path. The combination starting from 1 is the same as starting from 3,7,9, also starting from 2 is the same as starting from 4,6,8. Which gives:
int res = 0;
for (int i = m; i <= n; i++) {
res += dfs(i - 1, used, skip, 1) * 4;
res += dfs(i - 1, used, skip, 2) * 4;
res += dfs(i - 1, used, skip, 5);
}
return res;
1240. Tiling a Rectangle with the Fewest Squares
Go through every point in the rectangle, starting from (0,0), (0,1), ..., (n, m).
If rect[r,..., r+k][c, ..., c+k] is an available area, then cover a k*k square starting at point (r,c).
Try every possible size of square k * k, where k = min(n-r, m-c).
Optimzation: If cnt >= ans, then stop.
int res = Integer.MAX_VALUE;
public int tilingRectangle(int n, int m) {
dfs(0, 0, new boolean[m][n], 0);
return res;
}
private void dfs(int r, int c, boolean[][] rect, int count) {
int n = rect.length, m = rect[0].length;
if (count >= res) return;
if (r >= n) {
res = count;
return;
}
if (c >= m) {
dfs(r + 1, 0, rect, count);
return;
}
if (rect[r][c]) {
dfs(r, c + 1, rect, count);
return;
}
for (int k = Math.min(n - r, m - c); k >= 1 && isValid(rect, r, c, k); k--) {
cover(rect, r, c, k);
dfs(r, c + 1, rect, count + 1);
uncover(rect, r, c, k);
}
}
private boolean isValid(boolean[][] rect, int r, int c, int k) {
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (rect[r + i][c + j]) return false;
}
}
return true;
}
private void cover(boolean[][] rect, int r, int c, int k) {
for(int i = 0; i < k; i++){
for(int j = 0; j < k; j++){
rect[r+i][c+j] = true;
}
}
}
private void uncover(boolean[][] rect, int r, int c, int k) {
for(int i = 0; i < k; i++){
for(int j = 0; j < k; j++){
rect[r+i][c+j] = false;
}
}
}
