在原项目的基础上，尽量保持了原有的结构划分，并做了一点微小的工作：

- 调整部分内容，新增了几种算法

- [二叉树](./data_structure/binary_tree.md)

- [滑动窗口](./basic_algorithm/slide_window.md)

- [递归算法](./basic_algorithm/recursion.md)

- [回溯算法](./basic_algorithm/backtrack.md)

- [快速选择](./advanced_algorithm/quick_select.md)

- [三向切分快速排序](./advanced_algorithm/three_way_quick_sort.md)

- [二进制运算](./advanced_algorithm/binary_op.md)

1. 巩固基础：先从数据结构的基础题做起，掌握常见数据结构以及对应操作的实现

2. 算法专题：推荐按类型刷题，在几天之内做完同一种类型的题目，可以迅速理解

3. 查漏补缺：对于某些不常见的特殊解法，在最后快速刷掉，务必留下印象

本项目采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议</a>进行许可。

回溯法（backtrack）常用于遍历列表所有子集，是 DFS 深度搜索一种，一般用于全排列，穷尽所有可能，遍历的过程实际上是一个决策树的遍历过程。时间复杂度一般 O(N!)，它不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

result = []

func backtrack(选择列表,路径):

if 满足结束条件:

result.add(路径)

return

for 选择 in 选择列表:

做选择

backtrack(选择列表,路径)

撤销选择

核心就是从选择列表里做一个选择，然后一直递归往下搜索答案，如果遇到路径不通，就返回来撤销这次选择。

public List<List<Integer>> subsets(int[] nums) {

// 保存中间结果

List<Integer> subSet = new ArrayList<>();

// 保存最终结果

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

backtrack(nums, 0, subSet, result);

return result;

}

private void backtrack(int[] nums, int pos, List<Integer> subSet, List<List<Integer>> result) {

// 把临时结果复制出来保存到最终结果

result.add(new ArrayList<>(subSet));

for (int i = pos; i < nums.length; i++) {

// 选择、处理结果、再撤销选择

subSet.add(nums[i]);

backtrack(nums, i+1, subSet, result);

subSet.remove(subSet.size() - 1);

}

}

public List<List<Integer>> subsets(int[] nums) {

// 保存中间结果

List<Integer> subSet = new ArrayList<>();

// 保存最终结果

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

// 先排序

Arrays.sort(nums);

backtrack(nums, 0, subSet, result);

return result;

}

private void backtrack(int[] nums, int pos, List<Integer> subSet, List<List<Integer>> result) {

// 把临时结果复制出来保存到最终结果

result.add(new ArrayList<>(subSet));

for (int i = pos; i < nums.length; i++) {

// 排序之后，如果再遇到重复元素，则不选择此元素

if (i != pos && nums[i] == nums[i-1]) {

continue;

}

// 选择、处理结果、再撤销选择

subSet.add(nums[i]);

backtrack(nums, i+1, subSet, result);

subSet.remove(subSet.size() - 1);

}

}

思路：需要记录已经选择过的元素，满足条件的结果才进行返回。这里要注意在做选择时记录，回溯时撤销。

public List<List<Integer>> permute(int[] nums) {

List<Integer> list = new ArrayList<>();

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

// 标记这个元素是否已经添加到结果集

boolean[] visited = new boolean[nums.length];

backtrack(nums, visited, list, result);

return result;

}

private void backtrack(int[] nums, boolean[] visited, List<Integer> list, List<List<Integer>> result) {

if (list.size() == nums.length) {

result.add(new ArrayList<>(list));

return;

}

for (int i = 0; i < nums.length; i++) {

// 已经添加过的元素，直接跳过

if (visited[i]) {

continue;

}

// 添加元素

list.add(nums[i]);

visited[i] = true;

backtrack(nums, visited, list, result);

// 移除元素

list.remove(list.size() - 1);

visited[i] = false;

}

}

public List<List<Integer>> permuteUnique(int[] nums) {

List<Integer> list = new ArrayList<>();

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

// 标记这个元素是否已经添加到结果集

boolean[] visited = new boolean[nums.length];

// 先排序

Arrays.sort(nums);

backtrack(nums, visited, list, result);

return result;

}

private void backtrack(int[] nums, boolean[] visited, List<Integer> list, List<List<Integer>> result) {

if (list.size() == nums.length) {

result.add(new ArrayList<>(list));

return;

}

for (int i = 0; i < nums.length; i++) {

// 已经添加过的元素，直接跳过

if (visited[i]) {

continue;

}

// 上一个元素和当前相同，并且没有访问过就跳过

if (i != 0 && nums[i] == nums[i-1] && !visited[i-1]) {

continue;

}

list.add(nums[i]);

visited[i] = true;

backtrack(nums, visited, list, result);

list.remove(list.size() - 1);

visited[i] = false;

}

}

public List<List<Integer>> combinationSum(int[] candidates, int target) {

List<Integer> answer = new ArrayList();

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

// 先排序

Arrays.sort(candidates);

backtrack(candidates, 0, target, answer, result);

return result;

}

private void backtrack(int[] candidates, int pos, int target, List<Integer> answer, List<List<Integer>> result) {

if (target == 0) {

result.add(new ArrayList<>(answer));

}

for (int i = pos; i < candidates.length; i++) {

// 剪枝：后续元素都比目标大，直接break（比continue要快）

if (candidates[i] > target) {

break;

}

// 添加元素

answer.add(candidates[i]);

// 元素可以重复取，所以从当前位置继续

backtrack(candidates, i, target - candidates[i], answer, result);

// 移除元素

answer.remove(answer.size() - 1);

}

}

private final static Map<Character, String> map = new HashMap<>();

static {

map.put('2', "abc");

map.put('3', "def");

map.put('4', "ghi");

map.put('5', "jkl");

map.put('6', "mno");

map.put('7', "pqrs");

map.put('8', "tuv");

map.put('9', "wxyz");

}

public List<String> letterCombinations(String digits) {

StringBuilder builder = new StringBuilder();

List<String> result = new ArrayList<>();

backtrack(digits, 0, builder, result);

return result;

}

private void backtrack(String digits, int pos, StringBuilder builder, List<String> result) {

// 结束条件：到达末尾

if (pos == digits.length()) {

// 如果原字符串为空则没有对应的字母组合

if (pos != 0) {

result.add(builder.toString());

}

return;

}

for (char c : map.get(digits.charAt(pos)).toCharArray()) {

builder.append(c);

backtrack(digits, pos + 1, builder, result);

builder.deleteCharAt(builder.length() - 1);

}

}