遞增子序列

給你一個整數數組 nums ，找出并返回所有該數組中不同的遞增子序列，遞增子序列中 至少有兩個元素 。你可以按 任意順序 返回答案。
數組中可能含有重復元素，如出現兩個整數相等，也可以視作遞增序列的一種特殊情況。

• 這里仍然是樹層去重,不能排序后再去重,因為不能改變元素的相對位置
• 在哪一層取結果?(總結)
• 為什么不需要遞歸出口?

class Solution {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> path = new ArrayList<>();  
    public List<List<Integer>> findSubsequences(int[] nums) {  
        backTracking(nums,0);  
        return result;  
    }  
    public void backTracking(int[] nums,int startIndex){  
        if(path.size()>1){  
            result.add(new ArrayList<>(path));  
        }  
        HashSet<Integer> set = new HashSet<>();//set有去重的功能  
        for(int i = startIndex;i<nums.length;i++){  
            //根據樹形圖去重  
            // 非遞減判斷  
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {  
                continue;  
            }  
            // 當前層去重判斷  
            if (set.contains(nums[i])) {  
                continue;  
            }  
            set.add(nums[i]);  
            path.add(nums[i]);  
            backTracking(nums,i+1);  
            path.remove(path.size()-1);  
        }  
    }  
}

全排列

組合用startIndex標記,排列用used數組標記

class Solution {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> path = new ArrayList<>();  
    public List<List<Integer>> permute(int[] nums) {  
        boolean[] used = new boolean[nums.length];  
        backTracking(nums,used);  
        return result;  
    }  
    public void backTracking(int[] nums,boolean[] used){  
        if(path.size()==nums.length){  
            result.add(new ArrayList<>(path));  
            return;  
        }  
        for(int i = 0;i<nums.length;i++){  
            //if(used[i] == true) continue;  
            if(used[i]!=true){  
                used[i] = true;  
                path.add(nums[i]);  
                backTracking(nums,used);  
                path.removeLast();  
                used[i] = false;  
            }  
        }  
    }  
}

全排列2

給定一個可包含重復數字的序列 nums ，按任意順序 返回所有不重復的全排列。在上題中去重,和前面組合問題中去重一樣的邏輯

class Solution {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> path = new ArrayList<>();  
  
    public List<List<Integer>> permuteUnique(int[] nums) {  
        boolean[] used = new boolean[nums.length];  
        Arrays.sort(nums);  
        backTracking(nums, used);  
        return result;  
    }  
  
    public void backTracking(int[] nums, boolean[] used) {  
        if (path.size() == nums.length) {  
            result.add(new ArrayList<>(path));  
            return;  
        }  
        for (int i = 0; i < nums.length; i++) {  
            if (used[i] == true)  
                continue;  
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)  
                continue;//這里和組合中的去重一樣,used[i - 1] == false表示取的是第二個1
            used[i] = true;  
            path.add(nums[i]);  
            backTracking(nums, used);  
            path.removeLast();  
            used[i] = false;  
        }  
    }  
}

N皇后問題

按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。
n 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。
給你一個整數 n ，返回所有不同的 n 皇后問題 的解決方案。
每一種解法包含一個不同的 n 皇后問題 的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

這里的難點在于如何處理二維數組的回溯

class Solution {  
    List<List<String>> result = new ArrayList<>();  
    public List<List<String>> solveNQueens(int n) {  
        char[][] chessboard = new char[n][n];  
        for (char[] c : chessboard) {//將chessboard填滿.也可以用嵌套for來完成  
            Arrays.fill(c, '.');  
        }  
        backTracking(chessboard,n,0);  
        return result;  
    }  
    public void backTracking(char[][] chessboard,int n,int row){  
        if (row == n) {  
            result.add(Array2List(chessboard));  
            return;  
        }  
  
        for (int col = 0;col < n; ++col) {  
            if (isValid (row, col, n, chessboard)) {  
                chessboard[row][col] = 'Q';  
                backTracking(chessboard,n,row+1);  
                chessboard[row][col] = '.';  
            }  
        }  
    }  
    public List Array2List(char[][] chessboard) {  
        List<String> list = new ArrayList<>();  
  
        for (char[] c : chessboard) {  
            list.add(String.copyValueOf(c));  
        }  
        return list;  
    }  
  
  
    public boolean isValid(int row, int col, int n, char[][] chessboard) {  
        // 檢查列  
        for (int i=0; i<row; ++i) { // 相當于剪枝  
            if (chessboard[i][col] == 'Q') {  
                return false;  
            }  
        }  
  
        // 檢查45度對角線  
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {  
            if (chessboard[i][j] == 'Q') {  
                return false;  
            }  
        }  
  
        // 檢查135度對角線  
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {  
            if (chessboard[i][j] == 'Q') {  
                return false;  
            }  
        }  
        return true;  
    }  
}