class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //结果集
        List<List<Integer>> results = new ArrayList<>();
        //初始路径
        LinkedList<Integer> path = new LinkedList<>();
        conbineNext(candidates, target, 0, path, results);
        return results;
    }

    /**
     * 
     * @param candidates 数组
     * @param target 本级目标
     * @param startIndex 从哪个index开始遍历（去重）
     * @param path 到目前位置遍历的路径
     * @param results 结果集合
     */
    private void conbineNext(int[] candidates, int target, int startIndex, LinkedList<Integer> path, List<List<Integer>> results){
        if(target == 0){
            results.add(new ArrayList<>(path));
        }
        if(target < 0){
            return;
        }

        for(int i = startIndex; i< candidates.length;i++){
            path.add(candidates[i]);
            nextConbine(candidates, target - candidates[i], i, path, results);

            //巧妙的状态重置，实际上在这里做了剪枝
            path.removeLast();
        }
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        permuteNext(nums, used, new LinkedList<>(), results);
        return results;
    }

    private void permuteNext(int[] nums, boolean[] used, LinkedList<Integer> list, List<List<Integer>> results){
        if(list.size() == nums.length){
            results.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i<nums.length; i++){
            if(used[i]){
                continue;
            }

            used[i] = true;
            list.add(nums[i]);
            permuteNext(nums, used, list, results);

            //这边非常巧妙，比起我原本的算法，减少了构造新列表的成本，总耗时减少了许多
            used[i] = false;
            list.removeLast();
        }
    }
}

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        boolean[] isUsed = new boolean[nums.length];
        Arrays.sort(nums);
        next(nums, isUsed, path, results);
        return results;
    }

    private void next(int[] nums, boolean[] isUsed, LinkedList<Integer> path, List<List<Integer>> results){
        if(path.size() == nums.length){
            results.add(new ArrayList<>(path));
            return;
        }

        for(int i=0;i<nums.length;i++){
            //当前节点使用过返回
            //或者不是排序数组中重复元素的第一个，比如[1,1,2]，遍历第一层时不用index=1的1
            if(isUsed[i] || (i>0 && nums[i] == nums[i-1] && !isUsed[i-1])){
                continue;
            }

            isUsed[i] = true;
            path.addLast(nums[i]);

            next(nums, isUsed, path, results);

            isUsed[i] = false;
            path.removeLast();
        }
    }
}

class Solution {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        //从0层开始，结果集加入空集
        doSubsets(nums, 0, path, result);
        return result;
    }

    /**
    * curIndex，当层可以使用的元素下标起始点
    * 可使用的元素即从curIndex到(nums.length - 1)
    **/
    private void doSubsets(int[] nums, int curIndex, LinkedList<Integer> path, List<List<Integer>> result) {
        //记录本层路径
        result.add(new ArrayList<>(path));

        //处理当层从curIndex到(nums.length - 1)的元素
        for (int i = curIndex; i <= nums.length - 1; i++) {
            path.add(nums[i]);
            //下一层
            doSubsets(nums, i + 1, path, result);
            //处理完成后回复状态进而处理本层下一个
            path.removeLast();
        }
    }
}

class Solution {
    public  boolean exist(char[][] board, String word) {
        //两次循环，从二维数组中的每一个节点开始出发。
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (exist(board, i, j, word.toCharArray(), 0, new boolean[board.length][board[0].length])) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean exist(char[][] board, int i, int j, char[] word, int st, boolean[][] isUsed) {
        //成功终止条件，此时证明word已经全部找到
        if (st >= word.length) {
            return true;
        }

        //越界的直接返回不存在
        if (i >= board.length || j >= board[0].length || i < 0 || j < 0) {
            return false;
        }

        //当前元素和下一个需要的字符不相等，直接返回不存在
        if (board[i][j] != word[st]) {
            return false;
        }

        //用过的不能再用，返回不存在
        if (isUsed[i][j]) {
            return false;
        }

        //当前节点可用，标记已使用
        isUsed[i][j] = true;
        //尝试寻找下一层
        boolean exist = exist(board, i, j - 1, word, st + 1, isUsed) ||
                exist(board, i, j + 1, word, st + 1, isUsed) ||
                exist(board, i - 1, j, word, st + 1, isUsed) ||
                exist(board, i + 1, j, word, st + 1, isUsed);

        //如果不存在则当前路径失败，需要移除此时当前格子的占用
        if(!exist){
            isUsed[i][j] = false;
        }

        return exist;
    }
}

class Solution {
    private int sum = 0;

    private int sumTarget;

    public int findTargetSumWays(int[] nums, int target) {
        sumTarget = target;
        //下一个是+
        doFind(nums, 0, 0, true);
        //下一个是减
        doFind(nums, 0, 0, false);
        return sum;
    }

    public void doFind(int[] nums, int curSum, int curIndex, boolean isPlus) {
        if (isPlus) {
            curSum += nums[curIndex];
        } else {
            curSum -= nums[curIndex];
        }

        //如果当前是最后一个节点的就判断是否符合退出
        if (curIndex + 1 == nums.length) {
            if (curSum == sumTarget) {
                sum++;
            }
            return;
        }

        //下一层的+或-
        doFind(nums, curSum, curIndex + 1, true);
        doFind(nums, curSum, curIndex + 1, false);
    }
}