算法-回溯法

发表于 | 分类于 ，

组合问题

返回C(n,k)的所有可能值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class Combinations_77 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        if (n <= 0 || k <= 0 || k > n)
            return res;
        combine(n, k, 1, new ArrayList<>());
        return res;
    }
    /**
     * 求解C(n,k),
     * @param n
     * @param k
     * @param start
     * @param list
     */
    private void combine(int n, int k, int start, List<Integer> list) {
        if (list.size() == k) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i <= n- (k - list.size()) + 1; i++) {
            list.add(i);
            combine(n, k, i + 1, list);
            list.remove(list.size() - 1);
        }
    }
}

组合和等于target问题

给定一个数组,数组里面的值可以选无数次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class CombinationSum_39 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        combinationSum(candidates, target, new ArrayList<>(), 0);
        return res;
    }
    private void combinationSum(int[] candidates, int target, ArrayList<Integer> list, int pos) {
        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            if (target < candidates[i]) {
                return;
            } else {
                list.add(candidates[i]);
                combinationSum(candidates, target - candidates[i], list, i);
                list.remove(list.size() - 1);
            }
        }
    }
}

给定一个数组，数组中的数只能用一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class CombinationSumII_40 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        combinationSum(candidates, target, new ArrayList<>(), 0);
        return res;
    }
    private void combinationSum(int[] candidates, int target, ArrayList<Integer> list, int pos) {
        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            if (i != pos && candidates[i] == candidates[i-1])
                continue;
            if (target < candidates[i]) {
                return;
            } else {
                list.add(candidates[i]);
                combinationSum(candidates, target - candidates[i], list, i+1);
                list.remove(list.size() - 1);
            }
        }
    }
}

从1-9中选取k个数和为n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class CombinationSumIII_216 {
    List<List<Integer>> res = new ArrayList<>();
    public static final int[] nums = {1,2,3,4,5,6,7,8,9};
    public List<List<Integer>> combinationSum3(int k, int n) {
        if (k <= 0 || n <= 0)
            return res;
        combinationSum3(k, n, 0, new ArrayList<Integer>());
        return res;
    }
    private void combinationSum3(int k, int sum, int index, ArrayList<Integer> list) {
         if (k == 0 && sum == 0){
             res.add(new ArrayList<>(list));
             return;
         }
         for (int i = index; i < nums.length; i++) {
             if (sum < nums[index])
                 return;
             list.add(nums[i]);
             combinationSum3(k-1, sum- nums[i], i + 1, list);
             list.remove(list.size() - 1);
         }
    }
}

电话数字和字母映射的组合问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class LetterCombinationsOfAPhoneNumber_17 {
    private static final String[] letterMap  =  {" ", "","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    private List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if (digits == null || Objects.equals(digits, ""))
            return res;
        findCombation(digits, 0, "");
        return res;
    }
    private void findCombation(String digits, int index, String s) {
        if (index == digits.length()) {
            //保存s
            res.add(s);
            return;
        }
        char c = digits.charAt(index);
        String letters = letterMap[c - '0'];
        for (int i = 0; i < letters.length(); i++) {
            findCombation(digits, index + 1, s + letters.charAt(i));
        }
    }
}

N皇后问题

行，列，左右对角线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class NQueens_51 {
    private List<List<String>> res = new LinkedList<>();
    boolean[] col, dia1, dia2;
    public List<List<String>> solveNQueens(int n) {
        res.clear();
        List<Integer> row = new LinkedList<>();
        col = new boolean[n];
        dia1 = new boolean[2*n - 1];
        dia2 = new boolean[2*n - 1];
        putQueen(n, 0, row);
        return res;
    }
    /**
     *
     * @param n n皇后问题
     * @param index 第index行
     * @param row 数组，row[0]=i表示第0行第i列放皇后
     */
    private void putQueen(int n, int index, List<Integer> row) {
        if (index == n) {
            res.add(generateBoard(n, row));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!col[i] && !dia1[index + i] && !dia2[index-i+n-1]) {
                row.add(i);
                col[i] = true;
                dia1[index + i] = true;
                dia2[index-i+n-1] = true;
                putQueen(n, index + 1, row);
                col[i] = false;
                dia1[index + i] = false;
                dia2[index-i+n-1] = false;
                row.remove(row.size() -1);
            }
        }
    }
    private List<String> generateBoard(int n, List<Integer> row) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j ++) {
                if (j == row.get(i)) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            board.add(sb.toString());
        }
        return board;
    }
    public static void main(String[] args) {
        NQueens_51 queen = new NQueens_51();
        queen.solveNQueens(8);
        System.out.println(queen.res);
    }
}

WaterFlooding问题

太平洋，大西洋问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class PacificAtlanticWaterFlow_417 {
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> res = new LinkedList<>();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return res;
        }
        int n = matrix.length, m = matrix[0].length;
        boolean[][] pacific = new boolean[n][m];
        boolean[][] atlantic = new boolean[n][m];
        for(int i=0; i<n; i++){
            dfs(matrix, pacific, Integer.MIN_VALUE, i, 0);
            dfs(matrix, atlantic, Integer.MIN_VALUE, i, m-1);
        }
        for(int i=0; i<m; i++){
            dfs(matrix, pacific, Integer.MIN_VALUE, 0, i);
            dfs(matrix, atlantic, Integer.MIN_VALUE, n-1, i);
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (pacific[i][j] && atlantic[i][j])
                    res.add(new int[] {i, j});
        return res;
    }
    int[][]dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    public void dfs(int[][]matrix, boolean[][]visited, int height, int x, int y){
        int n = matrix.length, m = matrix[0].length;
        if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < height)
            return;
        visited[x][y] = true;
        for(int[]d:dir){
            dfs(matrix, visited, matrix[x][y], x+d[0], y+d[1]);
        }
    }
}

岛屿数量问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package leetcode.backtracking;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class NumbersOfIslands_200 {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != '1')
            return;
        grid[x][y] = '2';
        dfs(grid, x-1, y);
        dfs(grid, x+1,y);
        dfs(grid, x, y-1);
        dfs(grid, x, y + 1);
    }
}

环绕区域问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package leetcode.backtracking;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class SurroundedRegions_130 {
    int m;
    int n;
    public void solve(char[][] board) {
        if (board == null || board.length == 0)
            return;
        m = board.length;
        n = board[0].length;
        //从最外圈寻找O,找到之后dfs标记与O相连的O
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O')
                dfs(board, i, 0);
            if (board[i][n-1] == 'O')
                dfs(board, i, n-1);
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O')
                dfs(board, 0, j);
            if (board[m-1][j] == 'O')
                dfs(board, m-1, j);
        }
        //修改
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] != 'Z'){
                    board[i][j] = 'X';
                } else {
                    board[i][j] = 'O';
                }
            }
        }
    }
    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O')
            return;
        board[i][j] = 'Z';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }
}

字符串分隔问题

给定一个字符串，将字符串分成若干个子串，每个子串都为回文字符串，返回所有可能的分隔子串集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class PalindromePartitioning_131 {
    private List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s) {
        List<String> list = new ArrayList<>();
        partition(list, s, 0, "");
        return res;
    }
    private void partition(List<String> list, String s, int pos, String sub) {
        if (pos == s.length()) {
            if (sub.equals(""))
                res.add(new ArrayList<>(list));
            return;
        }
        String tmp = sub + s.charAt(pos);
        if (isPalindrome(tmp)) {
            list.add(tmp);
            partition(list, s, pos + 1, "");
            list.remove(list.size() - 1);
        }
        partition(list, s, pos + 1, tmp);
    }
    private boolean isPalindrome(String s) {
        for (int i = 0; i < s.length()/2; i += 1) {
            if (s.charAt(i) != s.charAt(s.length()-1-i))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        String s = "aab";
        System.out.println(new PalindromePartitioning_131().partition(s));
    }
}

给定一个字符串，返回其可能的IP值集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class RestoreIpAddress_93 {
    private List<String> res = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        int len = s.length();
        for (int i = 1; i < 4 && i < len - 2; i++) {
            for (int j = i + 1; j < i + 4 && j < len - 1; j++) {
                for (int k = j + 1; k < j + 4 && k < len; k++) {
                    String s1 = s.substring(0,i);
                    String s2 = s.substring(i,j);
                    String s3 = s.substring(j,k);
                    String s4 = s.substring(k,len);
                    if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)){
                        StringBuilder sb = new StringBuilder();
                        sb.append(s1).append(".").append(s2).append(".").append(s3)
                                .append(".").append(s4);
                        res.add(sb.toString());
                    }
                }
            }
        }
        return res;
    }
    private boolean isValid(String s) {
        return s.length() <= 3 && s.length() != 0 && (s.charAt(0) != '0' || s.length() <= 1) && Integer.parseInt(s) <= 255;
    }
    public List<String> restoreIpAddresses1(String s) {
        dfs(new StringBuilder(), 0, s, 0, 0);
        return res;
    }
    /**
     * DFS方法，回溯法应用
     * @param sb 拼接的字符串
     * @param pos 字符串的下标
     * @param s 输入的字符串
     * @param num 组成的数字
     * @param dot 点的个数
     */
    private void dfs(StringBuilder sb, int pos, String s, int num, int dot) {
        //终止条件，当检查晚最后一个元素时，如果点为3个，将字符串添加到res中
        if (pos == s.length()) {
            if (dot == 3)
                res.add(sb.toString());
            return;
        }
        //pos时，检查将其添加到当前数字中是否小于255，小于说明可以添加，则将其添加过去，遍历下一位
        if (num * 10 + s.charAt(pos)-'0' <= 255) {
            if (pos == 0 || num != 0) {
                sb.append(s.charAt(pos));
                dfs(sb, pos + 1, s,num * 10 + s.charAt(pos)-'0', dot);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        //不管pos能否添加，都不添加，而直接加点，迭代下一位
        if (dot < 3 && pos > 0){
            sb.append(".");
            sb.append(s.charAt(pos));
            dfs(sb,pos + 1, s, s.charAt(pos) - '0', dot + 1);
            sb.deleteCharAt(sb.length() - 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

全排列问题

给定一个数组，给出数组的所有全排列，没有重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class Permutations_46 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        List<Integer> list = new ArrayList<>();
        dfs(list, nums,0, used);
        return res;
    }
    private void dfs(List<Integer> list, int[] nums, int pos, boolean[] used) {
        if (pos == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                list.add(nums[i]);
                used[i] = true;
                dfs(list, nums, pos + 1, used);
                used[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

给定一个数组，给出数组的所有全排列，有重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package leetcode.backtracking;
import sun.misc.Perf;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class PermutationsII_47 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0)
            return res;
        boolean[] used = new boolean[nums.length];
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        dfs(list, nums, used);
        return res;
    }
    private void dfs(List<Integer> list, int[] nums, boolean[] used) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i])
                continue;
            if (i > 0 && nums[i-1] == nums[i] && !used[i-1])
                continue;
            used[i] = true;
            list.add(nums[i]);
            dfs(list, nums, used);
            used[i] = false;
            list.remove(list.size()-1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {2,2,1,1};
        PermutationsII_47 p = new PermutationsII_47();
        p.permuteUnique(nums);
        System.out.println(p.res);
    }
}

子集问题

返回一个数组的所有子数组, 数组没有重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class SubSets_78 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0)
            return res;
        subsets(nums, 0, new ArrayList<Integer>());
        return res;
    }
    private void subsets(int[] nums, int index, ArrayList<Integer> list) {
        res.add(new ArrayList<>(list));
        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]);
            subsets(nums, i + 1, list);
            list.remove(list.size() - 1);
        }
    }
    public static void main(String[] args) {
        SubSets_78 s = new SubSets_78();
        int[] num = {1,2,3};
        s.subsets(num);
        System.out.println(s.res);
    }
}

返回一个数组的所有子数组, 数组有重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class SubSetsII_90 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null || nums.length == 0)
            return res;
        Arrays.sort(nums);
        subsets(nums, 0, new ArrayList<Integer>());
        return res;
    }
    private void subsets(int[] nums, int index, ArrayList<Integer> list) {
        if (nums.length == index) {
            res.add(new ArrayList<>(list));
            return;
        }
        list.add(nums[index]);
        subsets(nums, index + 1,list);
        list.remove(list.size() - 1);
        while (index + 1 < nums.length && nums[index + 1] == nums[index])
            index++;
        subsets(nums, index + 1, list);
    }
}

数独问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package leetcode.backtracking;
/**
 * Created by cdx0312
 * 2018/4/11
 */
public class Sudoku_Solver_37 {
    public void solveSudoku(char[][] board) {
        doSolve(board, 0, 0);
    }
    private boolean doSolve(char[][] board, int row, int col) {
        for (int i = row; i < 9; i++, col = 0) {
            for (int j = col; j < 9; j++) {
                if (board[i][j] != '.')
                    continue;
                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (doSolve(board, i, j + 1))
                            return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    private boolean isValid(char[][] board, int row, int col, char num) {
        int blkrow = row / 3 * 3, blkcol = col / 3 * 3;
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num || board[row][i] == num || board[blkrow + i / 3][blkcol + i % 3] == num)
                return false;
        }
        return true;
    }
}

给定一个二维数组，判断能否拼成相应的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package leetcode.backtracking;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class WorldSearch_79 {
    public boolean exist(char[][] board, String word) {
        boolean[][] flag = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++)
                if (seachWord(board, word, 0, i, j, flag))
                    return true;
        }
        return false;
    }
    private boolean seachWord(char[][] board, String word, int index, int x, int y, boolean[][] flag) {
        if (index == word.length() - 1)
            return board[x][y] == word.charAt(index);
        if (board[x][y] == word.charAt(index)) {
            flag[x][y] = true;
            if (x - 1 >= 0 && !flag[x-1][y] && seachWord(board, word, index+1,x-1, y, flag))
                return true;
            if (x + 1 < board.length && !flag[x+1][y] && seachWord(board, word, index + 1, x + 1, y, flag))
                return true;
            if (y-1 >= 0 && !flag[x][y-1] && seachWord(board, word, index + 1, x, y-1, flag))
                return true;
            if (y + 1 <board[0].length && !flag[x][y+1] && seachWord(board, word, index + 1, x, y+1, flag))
                return true;
            flag[x][y] = false;
        }
        return false;
    }
}

二进制表的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package leetcode.backtracking;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by cdx0312
 * 2018/4/10
 */
public class BinaryWatch_401 {
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        int[] nums1 = new int[]{8,4,2,1};
        int[] nums2 = new int[]{32,16,8,4,2,1};
        for (int i = 0; i <= num; i++) {
            List<Integer> list1 = generateDigit(nums1, i);
            List<Integer> list2 = generateDigit(nums2, num - i);
            for (int num1 : list1) {
                if (num1 >= 12)
                    continue;
                for (int num2 : list2) {
                    if (num2 >= 60)
                        continue;
                    res.add(num1 + ":"+ (num2 < 10 ? "0" + num2 : num2));
                }
            }
        }
        return  res;
    }
    private List<Integer> generateDigit(int[] nums, int count) {
        List<Integer> res = new ArrayList<>();
        generateDigit(nums, count, 0, 0, res);
        return res;
    }
    private void generateDigit(int[] nums, int count, int pos, int sum, List<Integer> res) {
        if (count == 0) {
            res.add(sum);
            return;
        }
        for (int i = pos; i < nums.length; i++) {
            generateDigit(nums, count - 1, i + 1, sum + nums[i], res);
        }
    }
}
Donate comment here