回溯法、【leetcode】51.52 N-Queens

什么是回溯

回溯是一种穷举，但与brute force有一些区别，回溯带了两点脑子的，并不多，brute force一点也没带。
如果用爬山来比喻：
第一点脑子是回溯知道回头；相反如果是brute force,发现走不通立刻跳下山摔死，换第二条命从头换一条路走。
第二点脑子是回溯知道剪枝；如果有一条岔路走不通，那这条路我们不走，就可以少走很多不必要走的路。

识别回溯问题

判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。
一般回溯的问题有三种：

1. Find a path to success 有没有解
2. Find all paths to success 求所有解
   1. 求所有解的个数
   2. 求所有解的具体信息

1. Find the best path to success 求最优解

还有一些爱混淆的概念：递归，回溯，DFS。
回溯是一种找路方法，搜索的时候走不通就回头换路接着走，直到走通了或者发现此山根本不通。
DFS是一种开路策略，就是一条道先走到头，再往回走一步换一条路走到头，这也是回溯用到的策略。在树和图上回溯时人们叫它DFS。
递归是一种行为，回溯和递归如出一辙，都是一言不合就回到来时的路，所以一般回溯用递归实现；当然也可以不用，用栈。

关于回溯的三种问题，模板略有不同，
第一种，返回值是true/false。
第二种，求个数，设全局counter，返回值是void；求所有解信息，设result，返回值void。
第三种，设个全局变量best，返回值是void。

求解模板

第一种，有没有解：

boolean solve(Node n) {
    if n is a leaf node {
        if the leaf is a goal node, return true
        else return false
    } else {
        for each child c of n {
            if solve(c) succeeds, return true
        }
        return false
    }
}

第二种，求所有的解：

void solve(Node n) {
    if n is a leaf node {
        if the leaf is a goal node, count++, return;
        else return
    } else {
        for each child c of n {
            solve(c)
        }
    }
}

第三种，求最优解：

void solve(Node n) {
    if n is a leaf node {
        if the leaf is a goal node, update best result, return;
        else return
    } else {
        for each child c of n {
            solve(c)
        }
    }
}

八皇后问题

八皇后问题是大数学家高斯于1850年提出来的。该问题是在8×8的国际象棋棋盘上放置8个皇后，使得没有一个皇后能“吃掉”任何其他一个皇后，即没有任何两个皇后被放置在棋盘的同一行、同一列或同一斜线上。

扩展到一般情况就是：在n*n的棋盘上放置n和棋子，使得没有任何两个棋子在同一行、同一列或同一对角线上

思路

为了更好的理解回溯法，把这个问题分解成三个子问题：

1. 是否有这样的安放方法，满足游戏规则
2. 如果有，有多少个安放方式[leetcode 52]
3. 输出所有的安放方式[leetcode 51]

因为任何两个皇后不可能在同一行，所以我们可以采用如下的策略：
一行一行地安放皇后，每次放置皇后时需要确保此次放置的皇后跟之前已经放置的皇后没有处于同行、同列、同对角线上

需要下面两个函数：

1. 递归调用安放皇后（回溯法）
   逐个遍历可以安放皇后的位置，并递归调用取定下一层可以安放皇后的位置。直到最后一行的元素存在合法的放置位置，说明这是一种合理的安放情况。

1. 判断在某一点放queen是否合法

因为是一行一行放，所以可以保证不在一行上，需要判断同一列是否已经有皇后，以及左上方和右上方对角线方向是否已经有皇后。

另外还需要一个额外的空间标记当前皇后们安放的位置

代码

三个子问题的函数2，判断某一点是否可以放置皇后的函数一样：

//判断是否可以放置
bool isvalid(vector<vector<int>>& vec,int n, int k,int i){
     //k为当前行，i为当前列
    //判断左上方对角线是否有皇后
    int left = i;
    int up = k;
    while(left>=0&&up>=0){
        if(vec[up][left]==1)
            return false;
        left--;
        up--;
    }
    //判断右上方对角线是否有皇后
    int right = i;
    up = k;
    while(right<=n-1&&up>=0){
        if(vec[up][right]==1)
            return false;
        right++;
        up--;
    }
    //判断同列是否有元素
    for(int j = 0; j < k ;j++){
        if(vec[j][i]==1)
            return false;
    }
    return true;
}

其中vector<vector<int>>& vec是用来存放当前棋盘上放置的皇后位置。

差别在于回溯函数：

1. 是否存在

只需要找到一个满足条件的放置方案即可，逐行放置皇后，遇到不满足条件的情况就回退到上一层，继续寻找

//递归调用，判断皇后放置字当前点之后是否存在合法路径
void solve(vector<vector<int>>& vec,int n,int k,int l){
    //k为当前行，l为上一个的列
    //判断下一行是否有位置放置queen
    if(k==n-1){//最后一行，安放最后一个皇后
        for(int i=0;i <n;i++){
            if(isvalid(vec,n,k,i)){//如果存在合法安放情况，返回true
                return true;
            }
        }
    }
    else{
        for(int i = 0 ; i < n;i++){
            if(isvalid(vec,n,k,i)){//该点合理，将皇后放到该点，递归调用，判断下一层是否存在合法方案
                vec[k][i]=1;//房子皇后，标记皇后位置
                if (solve(vec,n,k+1,i))//下一层存在合法方案。返回true 否则回退，将皇后从该点移除
                    return true;
                vec[k][i]=0;//取消皇后位置标记
            }
        }
    }
}

bool ifNQueens(int n) {
    if(n==1)
        return true;
    if(n<4)
        return false
    vector<vector<int> > vec(n,vector<int>(n,0));//存储当前棋盘皇后位置
    //遍历首行放置皇后
    for(int i = 0 ; i < n;i++){
        vec[0][i]=1;
        if(solve(vec,n,1,i))//找到一条合法放置方式，返回true
            return true
        vec[0][i]=0;//否则恢复该点未被选中的棋盘，继续遍历下一个点
    }
}

2. 存在多少种安放方式 [leetcode] 51

在上面存在的基础之上，引入一个count计数变量，记录合法方案的数量，也就是没找到一个合法的安放方式就+1，知道遍历完所有的情况。

int resultNum = 0;
char[][] map;
//判断当前点是否合理
public boolean isValid(int i,int j){
//上方是否有点
for(int line = 0;line < i;line++){
if(map[line][j] == 'Q'){
return false;
}
}
//左上对角线是否有Q
int line = i-1;
int col = j-1;
while (line >= 0 && col >=0){
if(map[line][col] == 'Q'){
return false;
}
line--;
col--;
}
//右上方是否有Q
line = i-1;
col = j+1;
while (line >= 0 && col <map.length){
if(map[line][col] == 'Q'){
return false;
}
line--;
col++;
}
return true;
}

public void solve(int row){
if(row == map.length){
resultNum += 1;
return;
}
else{
for(int j = 0; j < map.length;j++){
if(isValid(row,j)){
map[row][j] = 'Q';
solve(row+1);
map[row][j] = '.';
}
}
}
}
public int totalNQueens(int n) {
//初始化map
this.map = new char[n][n];
for(int i = 0 ; i < n;i++){
for(int j = 0; j < n ;j ++){
map[i][j] = '.';
}
}
solve(0);
return resultNum;
}

3.输出所有的安放方式 [leetcode] 51

这次需要我们将所有合法的安放方式都输出，也就当找到一条合法安放方式时，就把当前的皇后放置情况输出到结果集。

另外根据题目输出结果格式要求：

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

对保存安放情况的变量类型作出修改：由原来的vector<vector<int>>& vec 变为vector<string>& vec

public class NQueen {
    char[][] map;
    //判断当前点是否合理
    public boolean isValid(int i,int j){
        //上方是否有点
        for(int line = 0;line < i;line++){
            if(map[line][j] == 'Q'){
                return false;
            }
        }
        //左上对角线是否有Q
        int line = i-1;
        int col = j-1;
        while (line >= 0 && col >=0){
            if(map[line][col] == 'Q'){
                return false;
            }
            line--;
            col--;
        }
        //右上方是否有Q
        line = i-1;
        col = j+1;
        while (line >= 0 && col <map.length){
            if(map[line][col] == 'Q'){
                return false;
            }
            line--;
            col++;
        }
        return true;
    }

    public void solve(List<List<String>> results,int row){
        if(row == map.length){
            //map转化为结果存入result
            List<String> res = new ArrayList<>();
            for(int i = 0 ;i < map.length;i++){
                String s = new String();
                for(int j = 0 ; j < map.length;j++){
                    s += map[i][j];
                }
                res.add(s);
            }
            results.add(res);
        }
        else{
            for(int j = 0; j < map.length;j++){
                if(isValid(row,j)){
                    map[row][j] = 'Q';
                    solve(results,row+1);
                    map[row][j] = '.';
                }
            }
        }
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        //初始化map
        this.map = new char[n][n];
        for(int i = 0 ; i < n;i++){
            for(int j = 0; j < n ;j ++){
                map[i][j] = '.';
            }
        }
        solve(results,0);
        return results;
    }
}

leetcode相关问题

全排列问题

Permutations

题目

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

> [
>   [1,2,3],
>   [1,3,2],
>   [2,1,3],
>   [2,3,1],
>   [3,1,2],
>   [3,2,1]
> ]
>
>

求给定数组中元素的排列组合，元素无重复

分析

分析元素排列的全部可能，典型的回溯，按照上面的模板做就好

代码

public class Permutations {
    boolean[] hasVisit;
    List<List<Integer>> results;
    List<Integer> result = new ArrayList<>();

    public void solve(int n,int[] nums){
        if (n == nums.length){
            //结果放入results
            List<Integer> temp = new ArrayList<>();
            temp.addAll(result);
            results.add(temp);
        }
        else {
            for(int i = 0;i < nums.length;i++){
                //该元素没有中出现过,放入result
                if(!hasVisit[i]){
                    hasVisit[i] = true;
                    result.add(nums[i]);
                    solve(n+1,nums);
                    hasVisit[i] = false;
                    result.remove(result.size()-1);
                }
            }
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        this.results = new ArrayList<>();
        this.hasVisit = new boolean[nums.length];

        solve(0,nums);
        return this.results;
    }
}

方法二：

固定-交换法

还有一种思路，这个更好理解一丢丢：

n个数的全排列，一共有n!n!种情况. （n个位置，第一个位置有n种，当第一个位置固定下来之后，第二个位置有n-1种情况…）

全排列的过程：

• 选择第一个字符
• 获得第一个字符固定下来之后的所有的全排列
  • 选择第二个字符
  • 获得第一+ 二个字符固定下来之后的所有的全排列

从这个过程可见，这是一个递归的过程。

所以这种方式也是通过固定一个元素，进行剩余元素的交换。缺点是，每次交换过后需要再次交换以回到上一层数组。

public class permutationsSwitch {
    List<List<Integer>> results = new ArrayList<>();
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void helper(int[] nums,int fixed){
        if(fixed == nums.length){
            List<Integer> result = new ArrayList<>();
            for(int e : nums){
                result.add(e);
            }
            results.add(result);
        }
        else{
            for(int i = fixed;i < nums.length;i++) {
                swap(nums,fixed,i);
                helper(nums,fixed +1);
                swap(nums,fixed,i);
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        helper(nums,0);
        return results;
    }
}

Permutations II

题目

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

> [
>   [1,1,2],
>   [1,2,1],
>   [2,1,1]
> ]
>

相比上一题，有重复元素

分析

遇到重复元素先排序，排序之后按照上题的思路，

注意：选取同一位置上的元素时，需要跳过重复元素

代码

public class PermutationsII {
    boolean[] hasVisit;
    List<List<Integer>> results;
    List<Integer> result = new ArrayList<>();
    public void solve(int n,int[] nums){
        if (n == nums.length){
            //结果放入results
            List<Integer> temp = new ArrayList<>();
            temp.addAll(result);
            results.add(temp);
        }
        else {
            int last = Integer.MIN_VALUE;//用以就该位置当前元素，下一轮遇到重复时需要跳过
            for(int i = 0;i < nums.length;i++){
                if(hasVisit[i] || (i != 0 && nums[i] == last)){//这里不可以用nums[i] == nums[i-1]
                    continue;
                }
                else {
                    hasVisit[i] = true;
                    result.add(nums[i]);
                    solve(n+1,nums);
                    hasVisit[i] = false;
                    result.remove(result.size()-1);
                    last = nums[i];
                }
            }
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        this.results = new ArrayList<>();
        this.hasVisit = new boolean[nums.length];
        Arrays.sort(nums);
        solve(0,nums);
        return this.results;
    }
}

Permutation Sequence

题目

The set [1,2,3,…,*n*] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

思路

对于n个字符组成的字符串{1,2,3,...,n}，取第k个数时，首先可以求出第一个数，即(k-1)/(n-1)!。

按照这样的方法依次求出每一位的数字。

代码

boolean[] hasVisit;
String result = new String();
public int calProduct(int n){
  int result = 1;
  while(n > 0){
    result *= n;
    n--;
  }
  return result;
}
public void solve(int n,int[] nums,int k){
  if(n == nums.length){
    return;
  }
  //要找到第nn个数字放到这里
  int nn = (k-1)/calProduct(nums.length-n-1);
  int j = 0;
  int num = 0;
  while(j < nums.length && num < nn){
    //如果nums[j]已经被用过了
    while(hasVisit[j]){
      j++;
    }
    num++;
    j++;
  }
  while(hasVisit[j]){
    j++;
  }
  result += nums[j];
  hasVisit[j] = true;
  solve(n+1,nums,k - (nn)*calProduct(nums.length-n-1));
}
public String getPermutation(int n, int k) {
  int[] nums = new int[n];
  for(int i = 1;i <= n;i++){
    nums[i-1] = i;
  }
  this.hasVisit = new boolean[nums.length];
  solve(0,nums,k);
  return result;
}

Binary Watch

题目

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

> Input: n = 1
> Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
>

>

Note:

• The order of output does not matter.
• The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
• The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

一个二进制手表，第一行有4个灯代表小时，第二行有6个灯代表分钟，给定一个num表示总共可以亮的灯的数量，返回所有可能的时间

注意：时间表示范围为0-11:59

思路

方法一：

分别对小时和分钟进行回溯，把num分配到两行上，计算小时和分钟的可能值，再进行组合输出

方法二：

利用Integer.bitCount() 函数计算二进制表示的1的个数，遍历00:00-11:59所有的时间，当小时和分钟的二进制表示中1的个数和为0时输出到结果集合。

代码

import java.util.ArrayList;
import java.util.List;

public class BinaryWatch {
    List<Integer> HorM;
    List<List<Integer>> HHs;
    List<List<Integer>> MMs;

    //计算时间,转化为字符串
    public String calTime(List<Integer> hour,List<Integer> minute){
        int[] hh = {8,4,2,1};
        int[] mm = {32,16,8,4,2,1};
        int h = 0;
        int m = 0;
        String res = new String();
        for(int i = 0; i < 4;i++){
            h += hour.get(i) * hh[i];
        }
        for(int i = 0; i < 6;i++){
            m += minute.get(i) * mm[i];
        }
        if(h <12 && m < 60){
            if(m<10){
                res = Integer.toString(h) + ":0" + Integer.toString(m);
            }
            else {
                res = Integer.toString(h) + ":" + Integer.toString(m);
            }
        }
        return res;
    }

    //计算小时或者分钟
    public void solve(int oneSum,List<Integer> HorM,int n){
        if(HorM.size() == n && oneSum == 0){
            List<Integer> temp = new ArrayList<>();
            temp.addAll(HorM);
            if(n==4){
                HHs.add(temp);
            }
            else {
                MMs.add(temp);
            }

        }
        else if(HorM.size() == n && oneSum != 0){
            return;
        }
        else {
            HorM.add(0);
            solve(oneSum,HorM,n);
            HorM.remove(HorM.size()-1);
            HorM.add(1);
            solve(oneSum - 1,HorM,n);
            HorM.remove(HorM.size()-1);
        }
    }

    public List<String> readBinaryWatch(int num) {
        List<String> result = new ArrayList<>();
        //计算第一行最少和最多放置几个元素
        int min = Math.min(0,Math.max(0,num-8));
        int max = Math.min(4,num);
        for(int i = min ; i <= max;i++){
            HHs = new ArrayList<>();
            MMs = new ArrayList<>();
            HorM = new ArrayList<>();
            //i为第一行放置个数
            //计算小时数组
            solve(i,HorM,4);
            //计算分钟数组
            HorM = new ArrayList<>();
            solve(num - i,HorM,6);
            for(int ii = 0; ii < HHs.size();ii++){
                for(int jj = 0 ; jj < MMs.size();jj++){
                    String res = calTime(HHs.get(ii),MMs.get(jj));
                    if(!res.isEmpty()){
                        result.add(res);
                    }
                }
            }
        }
        return result;
    }
    public static void main(String[] args){
        BinaryWatch test = new BinaryWatch();
        List<String> result = test.readBinaryWatch(2);
        System.out.print(result);
    }
}

方法二：

class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        for (int h = 0; h < 12; h ++) {
            for (int m = 0; m < 60; m ++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == num) {
                    if (m < 10) {
                        res.add(h + ":" + "0" + m);
                    } else {
                        res.add(h + ":" + m);
                    }
                }
            }
        }
        return res;
    }
}

Next Permutation

题目

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

分析

如果数组是降序的，则这几个数组的组合中，后面没有了：

比如[9,7,6,5,4]，这几个数字是降序的，由这几个数字组成的排列中没有序号大于这个组合方式的了。

当数组中出现升序位置时，说明后面有编号大于此排列的排列情况

步骤：

1. 找到第一处升序数组[4,7]
2. 将升序位置与后面数组中最后一个大于该元素的位置交换[4,5]
3. 此时原来5位置的后面都比4小，前面都比4大，而且是降序，所以将后半段数组倒置即可。

代码

//交换两个位置
public void swap(int[] nums,int i,int j){
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}
//数组反转
public void reverse(int[] nums,int i,int j){
  while (i < j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
    i++;
    j--;
  }
}

public void nextPermutation(int[] nums) {
  int i = nums.length-1;
  //找第一次出现升序的地方
  while(i > 0){
    if(nums[i] > nums[i-1]){
      break;
    }
    i--;
  }
  if(i == 0){
    reverse(nums,0,nums.length-1);
  }
  else {
    //找到第一个比nums[i-1]小的数字
    int j = i+1;
    int target = nums[i-1];
    while(j < nums.length){
      if(nums[j] <= target){
        break;
      }
      j++;
    }
    swap(nums,i-1,j-1);
    reverse(nums,i,nums.length-1);
  }
}

组合问题

Combinations

题目

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

> [
>   [2,4],
>   [3,4],
>   [2,3],
>   [1,2],
>   [1,3],
>   [1,4],
> ]
>
>

给定n和k，给出$C(n,k)$ 的全部组合方式

分析

非常典型的回溯问题

思路就是从n个里面选择1个，然后再剩余的n-1个里面选择k-1个

代码

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

//一共1-n和数字，从start开始，选择k个
public void solve(int n,int start,int k){
  //k个都选完了，加入结果
  if(k == 0){
    List<Integer> temp = new ArrayList<>();
    temp.addAll(result);
    results.add(temp);
  }
  //遍历到最后了，但是没选够k个，返回
  else if(start == n+1){
    return;
  }
  else {
    //遍历从start右边的元素，选取一个，在剩下的元素中选取k-1个
    for(int i = start;i <= n;i++){
      result.add(i);
      solve(n,i+1,k-1);
      result.remove(result.size()-1);
    }
  }
}

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

Combination Sum

题目

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

> [
>   [7],
>   [2, 2, 3]
> ]
>

给一个数组和一个target.求数组中的元素和等于target的所有可能。元素可以多次取。

分析

回溯

代码

public class CombinationSum {
    List<Integer> result = new ArrayList<>();
    List<List<Integer>> results = new ArrayList<>();

    public void solve(int[] candidates, int target,int start){
        if(target == 0){
            List<Integer> temp = new ArrayList<>();
            temp.addAll(result);
            results.add(temp);
        }
        else if (target < 0 || start == candidates.length){
            return;
        }
        else {
            for(int i = start;i < candidates.length;i++){
                result.add(candidates[i]);
                solve(candidates,target-candidates[i],i);
                result.remove(result.size()-1);
            }
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        solve(candidates,target,0);
        return results;
    }
}

Combination Sum II

题目

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

> [
>   [1, 7],
>   [1, 2, 5],
>   [2, 6],
>   [1, 1, 6]
> ]
>

给一个有重数组和一个target.求数组中的元素和等于target的所有可能。元素不可以多次取。

分析

这道题与上一题的最大区别就是不能多次取！需要注意的地方就是递归进入时的i需要加一（跳过本元素）

代码

public class CombinationSum {
    List<Integer> result = new ArrayList<>();
    List<List<Integer>> results = new ArrayList<>();

    public void solve(int[] candidates, int target,int start){
        if(target == 0){
            List<Integer> temp = new ArrayList<>();
            temp.addAll(result);
            results.add(temp);
        }
        else if (target < 0 || start == candidates.length){
            return;
        }
        else {
            for(int i = start;i < candidates.length;i++){
                if(i > start  && candidates[i] == candidates[i - 1])continue; // 去重
                result.add(candidates[i]);
                solve(candidates,target-candidates[i],i+1);
                result.remove(result.size()-1);
            }
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates,target,0);
        return results;
    }

    public static void main(String[] args){
        CombinationSum test = new CombinationSum();
        int[] candidates = {2,3,6,7};
        int target = 7;
        List<List<Integer>> resuts = test.combinationSum(candidates,target);
        System.out.print(resuts);
    }
}

Combination Sum III

题目

Find all possible combinations of *k* numbers that add up to a number *n*, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

*Example 1:*

Input: *k* = 3, *n* = 7

Output:

> [[1,2,4]]
>
>

>

*Example 2:*

Input: *k* = 3, *n* = 9

Output:

> [[1,2,6], [1,3,5], [2,3,4]]
>

求k个数（0-9的数）的和为n的所有组合。

分析

还是回溯问题。

代码

public void solve(int k,int n, int start){
  if(k == 0 && n == 0){
    List<Integer> temp = new ArrayList<>();
    temp.addAll(result);
    results.add(temp);
  }
  else if(k < 0 || n < 0){
    return;
  }
  else {
    for(int i = start ; i <= 9; i++){
      result.add(i);
      solve(k-1,n-i,i+1);
      result.remove(result.size()-1);
    }
  }
}

其他

Count Numbers with Unique Digits

题目

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Credits:
Special thanks to @memoryless for adding this problem and creating all test cases.

给一个n。求x的个数，其中0<=x<=10n0<=x<=10n ，且x的每一位的数字都不相同。

思路

n位数的可能有如下：

0      （就是0）
1 位数 -> C(9,1)  (从1-9里随机挑选一个)
2 位数 -> C(9,1) * C(9,1)  (第一位从1-9挑，第二位与第一位不同即可，所以也是9种)
3 位数 -> C(9,1) * C(9,1) * C(8,1) (第一位从1-9挑，第二位与第一位不同，第三位与前两位不同)
...
n 位数

代码：
       public int countNumbersWithUniqueDigits(int n) {
        int num = 10;
        if(n == 0){
            return 1;
        }
        if(n == 1){
            return num;
        }
        else {
            int[] c = {9,8,7,6,5,4,3,2,1,0};
            int product = 9;
            int i = 0;
            while(i < n-1){
                product *= c[i];
                num += product;
                i++;
            }
        }
        return num;
    }

Beautiful Arrangement

题目

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:

1. The number at the ith position is divisible by i.
2. i is divisible by the number at the ith position.

Now given N, how many beautiful arrangements can you construct?

Example 1:

> Input: 2
> Output: 2
> Explanation: 
>
> The first beautiful arrangement is [1, 2]:
>
> Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
>
> Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
>
> The second beautiful arrangement is [2, 1]:
>
> Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
>
> Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
>

分析

回溯，遇到满足条件的sum++;

代码

public class BeautifulArrangement {
    boolean[] map;
    int[] result;
    int sum = 0;

    public boolean isValid(int idx,int val){
        if(idx % val == 0 || (idx !=0 && val % idx == 0)){
            return true;
        }
        else return false;
    }

    public void solve(int idx,int N){
        if(idx == N){
            sum++;
            return;
        }
        else {
            for(int i = 1; i <= N;i++){
                if(!map[i-1] && isValid(idx+1,i)){
                    result[idx] = i;
                    map[i-1] = true;
                    solve(idx+1,N);
                    map[i-1] = false;
                }
            }
        }
    }

    public int countArrangement(int N) {
        this.map = new boolean[N];
        this.result = new int[N];
        solve(0,N);
        return this.sum;
    }
}

Letter Combinations of a Phone Number

题目

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

> Input:Digit string "23"
> Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
>

分析

组合问题，回溯即可

代码

public class LetterCombinationsofaPhoneNumber {
    HashMap<Character, char[]> table = new HashMap<>();
    String result = new String();
    List<String> results = new ArrayList<>();

    private void buildTable(){
        table.put('1',new char[0]);
        table.put('2',new char[]{'a','b','c'});
        table.put('3',new char[]{'d','e','f'});
        table.put('4',new char[]{'g','h','i'});
        table.put('5',new char[]{'j','k','l'});
        table.put('6',new char[]{'m','n','o'});
        table.put('7',new char[]{'p','q','r','s'});
        table.put('8',new char[]{'t','u','v'});
        table.put('9',new char[]{'w','x','y','z'});
        table.put('0',new char[]{' '});
        table.put('#',new char[]{'#'});
        table.put('*',new char[]{'*'});
    }
    public void solve(String digits,int idx){
        if(idx == digits.length()){
            String temp = new String();
            temp += result;
            if(!temp.isEmpty()){
                results.add(temp);
            }
        }
        else {
            if(table.get(digits.charAt(idx)).length == 0){
                solve(digits,idx+1);
            }
            if(table.get(digits.charAt(idx)).length == 1){
                result += table.get(digits.charAt(idx))[0];
                solve(digits,idx+1);
                result = result.substring(0,result.length()-1);
            }
            else {
                for(int i = 0;i < table.get(digits.charAt(idx)).length;i++){
                    result += table.get(digits.charAt(idx))[i];
                    solve(digits,idx+1);
                    result = result.substring(0,result.length()-1);
                }
            }
        }
    }

    public List<String> letterCombinations(String digits) {
        buildTable();
        solve(digits,0);
        return results;
    }
    public static void main(String[] args){

        LetterCombinationsofaPhoneNumber test = new LetterCombinationsofaPhoneNumber();
        String digits = "22";
        test.buildTable();
        List<String> results = test.letterCombinations(digits);
        System.out.print(results);

    }
}

Generate Parentheses

题目

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

> [
>   "((()))",
>   "(()())",
>   "(())()",
>   "()(())",
>   "()()()"
> ]
>

分析

回溯，向2n个位置放‘(’ 或‘)’ 用变量rightNeed 表示右边还需要的‘)’数量，也就是当前‘(’ 与‘)’ 的数量差：

1. 如果放置过程中出现右括号必做括号多的情况，返回上一层，因为这种情况不可能是结果了，无需向下计算
2. 当2n个括号放置完毕，且左右括号相等时
3. 加入括号有两重方式，加入左括号或者右括号

代码

class Solution {
    List<String> results = new ArrayList<>();
    String result = new String();
    char[] parentheses;
    public void solve(int idx,int rightNeed,int n){
        if(rightNeed < 0){
            return;
        }
        if(idx == 2*n){
            if(rightNeed == 0){
                String temp = new String();
                temp += result;
                results.add(temp);
            }
            else {
                return;
            }
        }
        
        else {
            //加入括号分两种情况讨论：left和right
            result += '(';
            solve(idx+1,rightNeed+1,n);
            result = result.substring(0,result.length()-1);

            result += ')';
            solve(idx+1,rightNeed-1,n);
            result = result.substring(0,result.length()-1);
        }
    }
    public List<String> generateParenthesis(int n) {
        solve(0,0,n);
        return results;
    }
}

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle…

9×99×9 的数独，填入数字1-9，要求行列不重复，且每个宫内不重复。

boolean[][] usedinLine = new boolean[9][9];//第i行中是否用过数字k
boolean[][] usedinCol = new boolean[9][9];//第i列中是否用过数字k
boolean[][][] usedinBlock = new boolean[3][3][9];//第ij个格子中是否用过数字k

public boolean solve(char[][] board){
  for(int i = 0 ; i < 9;i++){
    for(int j = 0 ; j < 9;j++){
      if(board[i][j] != '.'){
        continue;
      }
      else {
        for (int val = 1; val <= 9; val++) {
          if (!usedinLine[i][val - 1] && !usedinCol[j][val - 1] && !usedinBlock[i / 3][j / 3][val - 1]) {
            usedinLine[i][val - 1] = true;
            usedinCol[j][val - 1] = true;
            usedinBlock[i / 3][j / 3][val - 1] = true;
            board[i][j] = (char) (val + 48);
            if (solve(board)) return true;
            usedinLine[i][val - 1] = false;
            usedinCol[j][val - 1] = false;
            usedinBlock[i / 3][j / 3][val - 1] = false;
            board[i][j] = '.';
          }
        }
        return false;
      }
    }
  }
  return true;
}
public void solveSudoku(char[][] board) {
  //初始化
  for(int i = 0 ; i < 9;i++){
    for(int j = 0 ; j < 9;j++){
      if(board[i][j] != '.'){
        usedinLine[i][board[i][j]-'1'] = true;
        usedinCol[j][board[i][j]-'1'] = true;
        usedinBlock[i/3][j/3][board[i][j]-'1'] = true;
      }
    }
  }
  solve(board);
}

Wildcard Matching

题目

Implement wildcard pattern matching with support for '?' and '*'.

> '?' Matches any single character.
> '*' Matches any sequence of characters (including the empty sequence).
>
> The matching should cover the entire input string (not partial).
>
> The function prototype should be:
> bool isMatch(const char *s, const char *p)
>
> Some examples:
> isMatch("aa","a") → false
> isMatch("aa","aa") → true
> isMatch("aaa","aa") → false
> isMatch("aa", "*") → true
> isMatch("aa", "a*") → true
> isMatch("ab", "?*") → true
> isMatch("aab", "c*a*b") → false
>

分析

被伤透了的一道题。。。凉凉

思路就是：两指针i,j + 回溯

1. 两指针所指元素相等或者j指向‘?’，两指针后移递归调用
2. 两指针指的元素不相等，j也没指向‘?’和‘*’，这种情况凑不成一样的了，回溯
3. 如果j指向‘*’i可以选择跳过0\1\2.…一直到可以跳到最后一个元素，然后j也向后跳一个，看后面的是否相等，也就是递归调用了

边界条件：

1. 两指针都指向末尾了，返回true
2. j到末尾了，i没有，返回false
3. i到末尾了，j没有，如果j后面都是*则返回true,否则不可能相等，返回true

写完了超时了，因为ij组合会重复计算，所以需要用dp,把算过的存下来

代码

public class WildcardMatching {
  public boolean solve(String s, String p,int i,int j){
    //边界条件
    //两指针都遍历到末尾
    if(i == s.length() && j == p.length()){
      return true;
    }
    //j遍历到末尾，i没有
    else if(j == p.length()){
      return false;
    }
    //i指针遍历到末尾，j没有
    else if(i == s.length()){
      //如果j后面都是*了，则可以相等
      while(j < p.length() && p.charAt(j) == '*'){
        j++;
      }
      if(j == p.length()){
        return true;
      }
      //如果j后面不是全是*则一定不可以
      else return false;
    }
    //遇到*，i可以继续向后遍历，判断是否相等，回溯
    else if(p.charAt(j) == '*'){
      while(i <= s.length()){
        if(solve(s,p,i,j+1)) return true;
        i++;
      }
      return false;
    }

    //遇到？或者两个字符相等，继续匹配下一个
    else if(p.charAt(j) == '?' || s.charAt(i) == p.charAt(j)){
      return solve(s,p,i+1,j+1);
    }
    //两字符单纯地不相等
    else {
      return false;
    }
  }

  public boolean isMatch(String s, String p) {
    return solve(s,p,0,0);
  }
  public static void main(String[] args){
    WildcardMatching test = new WildcardMatching();
    String s = "a";
    String p = "aa";
    boolean a = test.solve(s,p,0,0);
    System.out.print(a);
  }
}

改进DP：

int[][] dp;
public int solve(String s, String p,int i,int j){
  //计算过了 直接返回
  if(dp[i][j] != 0){
    return dp[i][j];
  }
  //边界条件
  //两指针都遍历到末尾
  if(i == s.length() && j == p.length()){
    dp[i][j] = 1;
    return dp[i][j];
  }
  //j遍历到末尾，i没有
  else if(j == p.length()){
    dp[i][j] = -1;
    return dp[i][j];
  }
  //i指针遍历到末尾，j没有
  else if(i == s.length()){
    //如果j后面都是*了，则可以相等
    while(j < p.length() && p.charAt(j) == '*'){
      j++;
    }
    if(j == p.length()){
      dp[i][j] = 1;
    }
    //如果j后面不是全是*则一定不可以
    else dp[i][j] = 0;
    return dp[i][j];
  }
  //遇到*，i可以继续向后遍历，判断是否相等，回溯
  else if(p.charAt(j) == '*'){
    dp[i][j] = -1;
    while(i <= s.length()){
      if(solve(s,p,i,j+1) == 1){
        dp[i][j] = 1;
        return dp[i][j];
      }
      i++;
    }
    return dp[i-1][j];
  }

  //遇到？或者两个字符相等，继续匹配下一个
  else if(p.charAt(j) == '?' || s.charAt(i) == p.charAt(j)){
    dp[i][j] = solve(s,p,i+1,j+1);
    return dp[i][j];
  }
  //两字符单纯地不相等
  else {
    dp[i][j] = -1;
    return dp[i][j];
  }

}

public boolean isMatch(String s, String p) {
  dp = new int[s.length()+1][p.length()+1];
  solve(s,p,0,0);
  return dp[s.length()][p.length()]==1;
}

Regular Expression Matching

题目

Implement regular expression matching with support for '.' and '*'.

> '.' Matches any single character.
> '*' Matches zero or more of the preceding element.
>
> The matching should cover the entire input string (not partial).
>
> The function prototype should be:
> bool isMatch(const char *s, const char *p)
>
> Some examples:
> isMatch("aa","a") → false
> isMatch("aa","aa") → true
> isMatch("aaa","aa") → false
> isMatch("aa", "a*") → true
> isMatch("aa", ".*") → true
> isMatch("ab", ".*") → true
> isMatch("aab", "c*a*b") → true
>

分析

.可代表任意一个字母

* 和它前面的字母组合m在一起，可以用于表示0或任意多个m

思路就是两指针，从后向前匹配，当遇到*时，有两种选择：

1. 匹配s中的0个（j-2,i不变），继续向后递归
2. 匹配s中的1个（j不变,i-1），继续向后递归
3. 多个的情况包含在2中

代码

public class RegularExpressionMatching {
    public boolean solve(String s, String p,int i,int j){
        if(i < 0 && j < 0){return true;}
        else if(j < 0){ return false; }
        else if(i < 0){
            if(p.charAt(j) == '*'){
                return solve(s,p,i,j-2);
            }
            else {
                return false;
            }
        }

        else if(p.charAt(j) == '*'){
            //如果*前面一个是.或者是跟i指向的字母一样，可以选择匹配1个或者不匹配
            if(p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i)){
                return solve(s, p,i-1,j) || //匹配了s中的1个字符，j向前移两位，继续，这里匹配了多个字符的情况包含在后续的计算中了
                        solve(s,p,i,j-2);//匹配了s中的0个字符，j向前移两位，继续
            }
            //如果*前面不是.也不和i指向的数字一样，只能让他复制0个，继续往后判断
            else {
                return  solve(s, p,i,j-2);//匹配了s中的0个字符，j向前移两位，继续
            }
        }
        else if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'){
            return solve(s,p,i-1,j-1);
        }
        //指向字母不一样
        else {return false;}

    }
    public boolean isMatch(String s, String p) {
        return solve(s,p,s.length()-1,p.length()-1);
    }
    public static void main(String[] args){
        RegularExpressionMatching test = new RegularExpressionMatching();
        String s = "aab";
        String p = "c*a*b";
        boolean a = test.isMatch(s,p);
        System.out.print(a);
    }
}

Subsets II

题目

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

> [
>   [2],
>   [1],
>   [1,2,2],
>   [2,2],
>   [1,2],
>   []
> ]
>

分析

遇到重复元素先排序，然后回溯。需要注意的是遇到重复的元素需要跳过，但是只有在本位置用过的才不可以用相同元素，所以需要加一个flag来验证一下

代码

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

public void solve(int[] nums,int idx){
  boolean flag = false;
  if(idx == nums.length){return;}
  else{
    for(int i = idx ; i < nums.length;i++){
      if(i > 0 && nums[i] == nums[i-1] && flag){
        continue;
      }
      result.add(nums[i]);
      List<Integer> temp = new ArrayList<>();
      temp.addAll(result);
      results.add(temp);
      solve(nums,i+1);
      result.remove(result.size()-1);
      flag = true;//记录在本位置是否用过
    }
  }
}

public List<List<Integer>> subsetsWithDup(int[] nums) {
  Arrays.sort(nums);
  results.add(new ArrayList<>());
  solve(nums,0);
  return results;
}

Increasing Subsequences

题目

---

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:

> Input: [4, 6, 7, 7]
> Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
>
>

>

Note:

1. The length of the given array will not exceed 15.
2. The range of integer in the given array is [-100,100].
3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

给定数组，列举所有递增子序列

分析

回溯

如果加入的元素比result中最后一个元素的，就加入结果集合，否则不加入，继续向后。对于重复元素，需要跳过，这里元素无法排序，所以需要一个额外的数组维护元素是否出现过。

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class IncreasingSubsequences {
  List<List<Integer>> results = new ArrayList<>();
  List<Integer> result = new ArrayList<>();


  public void solve(int[] nums,int idx){
    boolean[] flag= new boolean[201];
    if(idx == nums.length){return;}
    else{
      for(int i = idx ; i < nums.length;i++){
        if(flag[nums[i]+100]){
          continue;
        }
        //如果当前result里没有元素或者当前元素比result里面的最后一个元素大，加入元素
        if(result.size() == 0 || nums[i] >= result.get(result.size()-1)){
          result.add(nums[i]);
          flag[nums[i]+100] = true;//标志本轮这个元素用过了
          if(result.size() > 1){//如果当前子序列长度大于1,加入结果集
            List<Integer> temp = new ArrayList<>();
            temp.addAll(result);
            results.add(temp);
          }
          solve(nums,i+1);//不管是不是加入结果集了，都要继续下一层
          result.remove(result.size()-1);//有nums[i]的计算完毕，将其移除
        }
      }
    }
  }

  public List<List<Integer>> findSubsequences(int[] nums) {
    solve(nums,0);
    return results;
  }
  public static void main(String[] args){
    IncreasingSubsequences test = new IncreasingSubsequences();
    int[] nums = {4,6,7,7};
    List<List<Integer>> res = test.findSubsequences(nums);
    System.out.print(res);
  }
}

Gray Code

题目

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

> 00 - 0
> 01 - 1
> 11 - 3
> 10 - 2
>
>

>

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

分析

格雷码是很经典的问题，规则其实很简单，在二进制形式下，任何相邻的两个值的二进制表示形式只有一位是不同的，我们可以找找规律。

一位就是简单的：0,1

两位是：00,01,11,10

三位是：000,001,011,010,110,111,101,100

发现什么规律没有？我们把一位的两个数，前面加上0，就是二位的头两个数，前面加上1再反序，就是二位的后两个数。把二位的前面加上0，就是三位的头四个数，把二位的前面加上1再反过来，就是三位的后四个数。

也就是说，对于每多一位的格雷码，前面一半的第一位都是0，后面一半的第一位都是1，其余的位，前后两半正好是中间对称的，前面一半就是少一位的格雷码序列，后面一半时把其反序。

知道这个规律就好做了，我们可以递归来做，每次取n-1位的格雷码来做上述操作，对于一位的格雷码，直接赋值是0,1就可以了。

不过题目要求返回的是十进制数，而不是字符串，所以我们最好直接操作十进制数，这里前面加0其实就不用做什么，前面加1的话可以将1左移n-1位然后与各个数字相加即可。

注意题目说的n是非负数，所以要考虑n=0的情况，测试用例的n=0时返回的是0。

代码

public List<Integer> grayCode(int n) {
  List<Integer> results = new ArrayList<>();
  if(n == 0){
    results.add(0);
    return results;
  }

  results.add(0);
  results.add(1);

  if(n == 1){ return results;}
  int i = 1;
  while(i < n){
    int len = results.size();
    while(len > 0){
      int delta = 1<<i;
      results.add(results.get(len-1) + delta);
      len--;
    }
    i++;
  }
  return results;
}

参考

liuqi627的博客
Jason_Yuan的博客