# Divide and conquer, backtracking algorithm

## I. divide and conquer algorithm

### 1. How to understand divide and conquer algorithm

Divide and conquer algorithm is to divide the original problem into n sub problems with small scale and similar structure to the original problem, solve these sub problems recursively, and then combine the results to get the solution of the original problem.

In the recursive implementation of divide and conquer algorithm, each layer of recursion involves three operations as follows:

• Decomposition: decompose the original problem into a series of subproblems
• Solution: recursively solve each subproblem. If the subproblem is small enough, directly solve it.
• Merge: merge the results of sub problems into the original problems

The problems that divide and conquer algorithm can solve generally need to meet the following conditions:

• The original problem has the same pattern as the small problem
• The subproblem decomposed from the original problem can be solved independently, and there is no correlation between subproblems.
• There are decomposition termination conditions, that is, when the problem is small enough, it can be solved directly
• The subproblem can be merged into the original problem, and the complexity of the merging operation cannot be too high, otherwise it will not reduce the overall complexity of the algorithm.

### 2. Problems related to divide and conquer algorithm

#### 1),LeetCode50: Pow(x, n)

To realize pow(x, n), that is, to calculate the N-power function of X

Example 1:

```Input: 2.00000, 10
Output: 1024.00000
```

Example 2:

```Input: 2.10000, 3
Output: 9.26100
```

Example 3:

```Input: 2.00000, - 2
Output: 0.25000
Explanation: 2-2 = 1 / 22 = 1 / 4 = 0.25
```

Explain:

```-100.0 < x < 100.0
n is a 32-bit signed integer with a value range of [− 231, 231 − 1]
```

Explanation:

```    public double myPow(double x, int n) {
if (n < 0) {
x = 1 / x;
n = -n;
}
return helper(x, n);
}

private double helper(double x, int n) {
if (n == 0) return 1.0;
double half = helper(x, n / 2);
if (n % 2 == 0) return half * half;
else return half * half * x;
}
```

#### 2),LeetCode169: Seek mode

Given an array of size n, find the mode. Mode refers to an element that occurs more than n/2n/2n/2 times in an array

You can assume that an array is not empty and that there is always a mode for a given array

Example 1:

```Input: [3,2,3]
Output: 3
```

Example 2:

```Input: [2,2,1,1,1,2,2]
Output: 2
```

Explanation:

```    public int majorityElement(int[] nums) {
return helper(0, nums.length - 1, nums);
}

private int helper(int low, int high, int[] nums) {
if (low == high) return nums[low];
int mid = low + ((high - low) >> 1);
int left = helper(low, mid, nums);
int right = helper(mid + 1, high, nums);
if (left == right) return left;
int leftCount = countInRange(left, low, high, nums);
int rightCount = countInRange(right, low, high, nums);
return leftCount > rightCount ? left : right;
}

private int countInRange(int num, int low, int high, int[] nums) {
int count = 0;
for (int i = low; i <= high; ++i) {
if (nums[i] == num) count++;
}
return count;
}
```

## 2. Backtracking algorithm

### 1. How to understand backtracking algorithm

The processing idea of backtracking is similar to enumeration search. By enumerating all the solutions, we can find the solution that meets the expectation. In order to enumerate all possible solutions regularly and avoid omission and repetition, we divide the problem solving process into several stages. At each stage, we will face a fork in the road. First, we will choose a road at will. When we find that the road is impassable (not in line with the expected solution), we will go back to the previous fork in the road and choose another way to continue.

### 2. Related topics of backtracking algorithm

#### 1),LeetCode22: bracket-generating

Given that n represents the logarithm of generating parentheses, please write a function that can generate all possible and valid combinations of parentheses.

For example, given n=3, the result is:

```[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
```

Explanation:

```    public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
helper(0, 0, n, "", list);
return list;
}

private void helper(int left, int right, int max, String currentStr, List<String> list) {
if (left == max && right == max) {
return;
}
if (left < max) {
helper(left + 1, right, max, currentStr + "(", list);
}
if (right < left) {
helper(left, right + 1, max, currentStr + ")", list);
}
}
```

#### 2),LeetCode78: subset

Given a set of integer array nums without repeating elements, all possible subsets (power sets) of the array are returned.

**Note: * * the solution set cannot contain duplicate subsets

Example:

```Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
```

Explanation:

```    List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> subsets(int[] nums) {
if (nums.length == 0) return result;
helper(0, nums, new ArrayList<>());
return result;
}

private void helper(int level, int[] nums, List<Integer> list) {
if (level == nums.length) {
return;
}
helper(level + 1, nums, list);
helper(level + 1, nums, list);
list.remove(list.size() - 1);
}
```

#### 3),LeetCode17: Letter combination of telephone number

Explanation:

```    Map<Character, String> phone = new HashMap<Character, String>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
List<String> result = new ArrayList<>();

public List<String> letterCombinations(String digits) {
if (digits.length() == 0) return result;
helper(0, digits, "");
return result;
}

private void helper(int level, String digits, String currentStr) {
if (level == digits.length()) {
return;
}
String latters = phone.get(digits.charAt(level));
for (int i = 0; i < latters.length(); ++i) {
helper(level + 1, digits, currentStr + latters.charAt(i));
}
}
```

#### 4),LeetCode46: Full Permutation

Given a sequence without repeating numbers, all possible permutations are returned

Example:

```Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
```

Explanation:

```    List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> permute(int[] nums) {
int[] visited = new int[nums.length];
helper(0, nums, visited, new Stack<>());
return result;
}

private void helper(int depth, int[] nums, int[] visited, Stack<Integer> stack) {
if (depth == nums.length) {
return;
}
for (int i = 0; i < nums.length; ++i) {
if (visited[i] == 1) continue;
visited[i] = 1;
stack.push(nums[i]);
helper(depth + 1, nums, visited, stack);
visited[i] = 0;
stack.pop();
}
}
```

#### 5),LeetCode47: Full array II

Given a sequence that can contain repeating numbers, all non repeating permutations are returned.

Example:

```Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
```

Explanation:

```    List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> permuteUnique(int[] nums) {
int[] visited = new int[nums.length];
Arrays.sort(nums);
helper(0, nums, visited, new Stack<>());
return result;
}

private void helper(int depth, int[] nums, int[] visited, Stack<Integer> stack) {
if (depth == nums.length) {
return;
}
for (int i = 0; i < nums.length; ++i) {
if (visited[i] == 1) continue;
if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] != 1) continue;
visited[i] = 1;
stack.push(nums[i]);
helper(depth + 1, nums, visited, stack);
visited[i] = 0;
stack.pop();
}
}
```

#### 6),LeetCode77: combination

Given two integers n and k, return 1... The combination of all possible k numbers in n

Example:

```Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
```

Explanation:

```    List<List<Integer>> result = new LinkedList<>();

public List<List<Integer>> combine(int n, int k) {
return result;
}

private void helper(int first, int n, int k, LinkedList<Integer> list) {
if (list.size() == k) {
return;
}
for (int i = first; i <= n; ++i) {