class Solution {

    int n = 3;
    int N = n * n;
    //分别代表每一行、列、方块中0-9填写的数字出现的次数
    int [][] rows = new int[N][N + 1];
    int [][] columns = new int[N][N + 1];
    int [][] boxes = new int[N][N + 1];

    char[][] board=null;
    boolean sudokuSolved = false;

    public void solveSudoku(char[][] board) {
        this.board = board;
        // 初始化
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                char num = board[i][j];
                if (num != '.') {
                    int d = Character.getNumericValue(num);
                    placeNumber(d, i, j);
                }
            }
        }
        backtrack(0, 0);
    }

    public boolean couldPlace(int d, int row, int col) {
        /*
        * 检查该位置是否能放数字
        */
        int idx = (row / n ) * n + col / n;
        return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
    }
    
    public void placeNumber(int d, int row, int col) {
        /*
        Place a number d in (row, col) cell
        */
        int idx = (row / n ) * n + col / n;
    
        rows[row][d]++;
        columns[col][d]++;
        boxes[idx][d]++;
        board[row][col] = (char)(d + '0');
    }
    
    public void removeNumber(int d, int row, int col) {
        /*
        Remove a number which didn't lead to a solution
        */
        int idx = (row / n ) * n + col / n;
        rows[row][d]--;
        columns[col][d]--;
        boxes[idx][d]--;
        board[row][col] = '.';
    }
    
    public void placeNextNumbers(int row, int col) {
     
        if ((col == N - 1) && (row == N - 1)) {
          sudokuSolved = true;
        }
        // if not yet
        else {
          // if we're in the end of the row
          // go to the next row
          if (col == N - 1) backtrack(row + 1, 0);
            // go to the next column
          else backtrack(row, col + 1);
        }
    }

    public void backtrack(int row, int col) {
        /*
        Backtracking
        */
        // 如果这个位置为空
        if (board[row][col] == '.') {
          //从 0->9进行遍历
          for (int d = 1; d < 10; d++) {
            if (couldPlace(d, row, col)) {
              placeNumber(d, row, col);
              placeNextNumbers(row, col);
              // if sudoku is solved, there is no need to backtrack
              // since the single unique solution is promised
              if (!sudokuSolved) removeNumber(d, row, col);
            }
          }
        }
        else placeNextNumbers(row, col);
    }
}

class Solution {
    //存储每一行皇后放的位置
    int rows[];
    // 主对角线
    int hills[];
    // 次对角线
    int dales[];
    int n;
    List<List<String>> output ;
    // 皇后位置，用于最后的设置
    int queens[];

    public boolean isNotUnderAttack(int row, int col) {
        int res = rows[col] + hills[row - col + 2 * n] + dales[row + col];
        return (res == 0) ? true : false;
    }

    public List<List<String>> solveNQueens(int n) {
        output  =new ArrayList<>();
        this.n = n;
        rows = new int[n];
        //主对角线大一些是为了防止相减出现出现负数
        hills = new int[4 * n - 1];
        dales = new int[2 * n - 1];
        queens = new int[n];
    
        backtrack(0);
        return output; 
    }

    public void placeQueen(int row, int col) {
        queens[row] = col;
        rows[col] = 1;
        //表示那条对角线被填
        hills[row - col + 2 * n] = 1;  // "hill" diagonals
        dales[row + col] = 1;   //"dale" diagonals
    }

    public void removeQueen(int row, int col) {
        queens[row] = 0;
        rows[col] = 0;
        hills[row - col + 2 * n] = 0;
        dales[row + col] = 0;
    }

    public void addSolution() {
        List<String> solution = new ArrayList<String>();
        for (int i = 0; i < n; ++i) {
          int col = queens[i];
          StringBuilder sb = new StringBuilder();
          for(int j = 0; j < col; ++j) sb.append(".");
          sb.append("Q");
          for(int j = 0; j < n - col - 1; ++j) sb.append(".");
          solution.add(sb.toString());
        }
        output.add(solution);
    }

    public void backtrack(int row) {
        for (int col = 0; col < n; col++) {
          if (isNotUnderAttack(row, col)) {
            placeQueen(row, col);
            // 放满了
            if (row + 1 == n) addSolution();
              // if not proceed to place the rest
            else backtrack(row + 1);
            // backtrack
            removeQueen(row, col);
          }
        }
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root==null || (root.left==null && root.right==null))
            return root;

        root.left.next = root.right;
        //这一步很巧妙，利用了root已经设置好的next
        if(root.next != null){
            root.right.next = root.next.left;
        }
        //深度遍历
        connect(root.left);
        connect(root.right);
        return root;
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null || (root.right == null && root.left == null)) {
            return root;
        }
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
            root.right.next = getNextNoNullChild(root);
        }
        if (root.left == null) {
            root.right.next = getNextNoNullChild(root);
        }
        if (root.right == null) {
            root.left.next = getNextNoNullChild(root);
        }
        //这里要注意：先递归右子树，否则右子树根节点next关系没建立好，左子树到右子树子节点无法正确挂载
        root.right = connect(root.right);
        root.left = connect(root.left);
        return root;
    }
    
    /**
     * 一路向右找到有子节点的根节点
     */
    private  Node getNextNoNullChild(Node root) {
        while (root.next != null) {
            if (root.next.left != null) {
                return root.next.left;
            }
            if (root.next.right != null) {
                return root.next.right;
            }
            root = root.next;
        }
        return null;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums==null || nums.length<=1) {
            return null;
        }
        int []ans = new int[2];
        Map<Integer,Integer> helperMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (helperMap.containsKey(target-nums[i]) && helperMap.get(target-nums[i])!=i) {
                ans[0] = helperMap.get(target-nums[i]);
                ans[1] = i;
                break;
            }
            helperMap.put(nums[i],i);
        }

      
        if (ans[0]!=ans[1]) {
            return ans;
        }
        return null;
    }
}

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return null;
        }

        int p1 = 0;
        int p2 = numbers.length - 1;
        while (p1 < p2) {
            if (numbers[p1] + numbers[p2] == target) {
                return new int[] { p1+1, p2+1 };

            } else if (numbers[p1] + numbers[p2] < target) {
                ++p1;
            } else {
                --p2;
            }
        }

        return null;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);//利用排序解决重复问题
        int p1 =0;
        int p2 =nums.length-1;
        int target = 0; //target可以为任意数
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            p1=i+1;p2 = nums.length-1;
            //转化为两数之和
            while (p1<p2) {
                int sum = nums[i]+nums[p1]+nums[p2];
                 if(sum==target){
                    List<Integer> ans = new ArrayList<>();
                    ans.add(nums[i]);
                    ans.add(nums[p1]);
                    ans.add(nums[p2]);
                    res.add(ans);
                    //解决重复问题
                    while(p1<p2&&nums[p1]==nums[p1+1]){
                        p1++;
                    }
                    p1++;
                    while (p1<p2&&nums[p2]==nums[p2-1]) {
                        p2--;
                    }
                    p2--;
                }else if(sum<target){
                    p1++;
                }else if(sum>target){
                    p2--;
                }
            }
        }
        return res;
    }
}

class Solution {
    public int threeSumClosest(int[] nums, int target) {
         Arrays.sort(nums);
        int p1 =0;
        int p2 =nums.length-1;
        int closetNum = nums[0]+nums[1]+nums[2];
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            p1=i+1;p2 = nums.length-1;
            int sum = 0;
            //转化为两数之和
            while (p1<p2) {
                sum = nums[p1]+nums[p2]+nums[i];
                //改变closetNum
                if(Math.abs(sum-target)<Math.abs(closetNum-target)){
                    closetNum = sum;
                }

                if(sum==target){
                   return target;
                }else if(sum<target){
                   p1++;
                }else if(sum>target){
                   p2--;
                }
           }
        }
        return closetNum;
    }
}

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);//利用排序解决重复问题
        int p1 =0;
        int p2 =nums.length-1;
        //和三数之后思路相同
        for (int i = 0; i < nums.length-3; i++) {
            if(i > 0 && nums[i] == nums[i - 1]) continue;   //确保第一个数发生变化
           for (int j = i+1; j < nums.length-2; j++) {
               if(j>i+1 && nums[j] == nums[j - 1]) continue; //确保第二个数发生变化
               p1=j+1;p2 = nums.length-1;
               //转化为两数之和
               while (p1<p2) {
                    int sum = nums[i]+nums[j]+nums[p1]+nums[p2];
                    if(sum==target){
                       List<Integer> ans = new ArrayList<>();
                       ans.add(nums[i]);
                       ans.add(nums[j]);
                       ans.add(nums[p1]);
                       ans.add(nums[p2]);
                       res.add(ans);
                       //解决重复问题
                       while(p1<p2&&nums[p1]==nums[p1+1]){
                           p1++;
                       }
                       p1++;
                       while (p1<p2&&nums[p2]==nums[p2-1]) {
                           p2--;
                       }
                       p2--;
                   }else if(sum<target){
                       p1++;
                   }else if(sum>target){
                       p2--;
                   }
               }
           }
        }
        return res;
    }
}

class Solution {
    char[] str;
    char[] pattern;
    public boolean isMatch(String s, String p) {
          if (s==null||p==null) {
            return false;
        }
        this.str = s.toCharArray();
        this.pattern = p.toCharArray();
        return matchCore(0,0);
    }

     /***
     * 
     * @param sStart str 开始的位置
     * @param pStart pattern 开始的位置
     * @return
     */
    boolean matchCore(int sStart,int pStart){
        if (sStart==str.length && pStart==pattern.length) return true;
        if (sStart!=str.length && pStart==pattern.length) return false;

        //说明第二个为 *
        if (pStart<pattern.length-1 && pattern[pStart+1]=='*') {
            if (sStart!=str.length && (pattern[pStart]==str[sStart]||pattern[pStart]=='.')) {
                //相等时，需要进行判断
                //分别为 *当作一个，当作多个，当作没有
                return matchCore(sStart+1, pStart+2)||matchCore(sStart+1, pStart) || matchCore(sStart, pStart+2);
                
            }else{
                //不相等时，当这个*不存在
                return   matchCore(sStart, pStart+2);
            }
        }

      if (sStart!=str.length && (pattern[pStart]==str[sStart]||(pattern[pStart]=='.' )))
            return matchCore(sStart+1, pStart+1);

        return false;

    }
}

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        //代表s的i和p的j的匹配
        boolean[][] f = new boolean[m + 1][n + 1];
        //表示没有字符时
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                        //下面几种都行
                        //dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2];
                        //dp[i][j] = dp[i - 1][j] || dp[i - 1][j - 2] || dp[i][j - 2]
                    }
                }
                else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

class Solution {
    char[] str;
    char[] pattern;
    public boolean isMatch(String s, String p) {
        if (s==null||p==null) {
            return false;
        }
        this.str = s.toCharArray();
        this.pattern = p.toCharArray();
        return matchCore(0,0);
    }

     /***
     * 
     * @param sStart str开始的地方
     * @param pStart pattern 开始的位置 
     * @return
     */
    boolean matchCore(int sStart,int pStart){
        if (sStart==str.length && pStart==pattern.length) return true;
        if (sStart!=str.length && pStart==pattern.length) return false;
        // if(sStart>=str.length && pattern[pStart]!='*') return false;

        if(sStart<str.length && pattern[pStart]=='*'){
            //分别为 * 代表空、1个字符、多个字符
            return matchCore(sStart, pStart+1) || matchCore(sStart+1, pStart+1) || matchCore(sStart+1, pStart);
        }else if (sStart<str.length && pattern[pStart]==str[sStart]||(pattern[pStart]=='?')) {
            return matchCore(sStart+1, pStart+1);
        }else if (sStart==str.length && pattern[pStart]=='*') {
            return matchCore(sStart, pStart+1);
        }

        return false;
    }
}

class Solution {

    public boolean isMatch(String s, String p) {
 int m = s.length();
        int n = p.length();
        //dp[i][j表示 s 第i个 到p第j个是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <=n; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = true;
            }
            else {
                break;
            }
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }

}

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            }
            set.add(num);
        }
        return false;
    }
}

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 用散列表来维护这个kk大小的滑动窗口。
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; ++i) {
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; ++i) {
            // 返回set中大于或者等于给定元素的最小元素，如果不存在这样的元素,返回null.
            Integer s = set.ceiling(nums[i]);
            if (s != null && s <= nums[i] + t)
                return true;

            // 返回在这个集合中小于或者等于给定元素的最大元素，如果不存在这样的元素,返回null.
            Integer g = set.floor(nums[i]);
            if (g != null && nums[i] <= g + t)
                return true;
			//维持滑动窗口
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;

        int[] dp = new int[n];
        dp[0] = nums[0];
        if (n > 1) {
            dp[1] = Math.max(nums[0], nums[1]);
        }
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }
}

class Solution {
    public int rob(int[] nums) {
        int pre = 0, cur = 0, tmp;
        for (int num : nums) {
            tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }
}

class Solution {
    // 进行两次遍历，分别对0->n-2 和 1->n-1 进行求解
    public int rob(int[] nums) {
        if (nums.length == 0)
            return 0;
        if (nums.length == 1)
            return nums[0];
        return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                myRob(Arrays.copyOfRange(nums, 1, nums.length)));
    }

    private int myRob(int[] nums) {
        int pre = 0, cur = 0, tmp;
        for (int num : nums) {
            tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[] { 0, 0 };
        }

        // 分类讨论的标准是：当前结点偷或者不偷
        // 由于需要后序遍历，所以先计算左右子结点，然后计算当前结点的状态值
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        // dp[0]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点不偷
        // dp[1]：以当前 node 为根结点的子树能够偷取的最大价值，规定 node 结点偷
        int[] dp = new int[2];

        dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        dp[1] = node.val + left[0] + right[0];
        return dp;
    }
}

class Solution {
    private HashMap<Character, Character> mappings;
    public boolean isValid(String s) {
        if(s==null||s.length()==0) return true;
        this.mappings = new HashMap<Character, Character>();
        this.mappings.put(')', '(');
        this.mappings.put('}', '{');
        this.mappings.put(']', '[');
        Stack<Character> charStack = new Stack<>();
       
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (this.mappings.containsKey(ch)) {
                char topElement = charStack.empty() ? '#' : charStack.pop();
                if (topElement != this.mappings.get(ch)) {
                    return false;
                }

            }else{
                charStack.push(ch);                
            }
        }
        return charStack.isEmpty();
    }
}

class Solution {
    List<String> res = null;
    public List<String> generateParenthesis(int n) {
          res = new ArrayList<>();
        char [] Parenthesis = new char[2*n];
        for (int i = 0; i < Parenthesis.length; i++) {
            Parenthesis[i]='(';
        }
        dfs(Parenthesis,1,0);
        return res;
    }

     void dfs(char[] Parenthesis,int index,int count){
        if (count==Parenthesis.length/2) {
            res.add(String.valueOf(Parenthesis));
            return;
        }

        for (int i = index; i < Parenthesis.length; i++) {
            if (i+1<(count+1)*2) continue;
            Parenthesis[i] = ')';
            dfs(Parenthesis,i+1,count+1);
            Parenthesis[i]='(';
        }
    }
}

/**
 * 困难级别，以后需要回看一下
 */
public class longestValidParentheses {
    //动态规划
    public int LongestValidParentheses(String s) {
        int maxans = 0;
        int []dp = new int[s.length()];
        for (int i = 1; i < dp.length; i++) {
            if (s.charAt(i)==')') {

                if (s.charAt(i-1)=='(') {
                    //刚好凑一对
                    dp[i]=(i>2 ? dp[i-2] : 0)+2;
                }else if(i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '('){
                    //跟远方的凑成一对
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }

    //使用栈的方法进行
    public int LongestValidParentheses2(String s) {
        int maxans = 0;
        //将下标存进去
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }

    //贪心算法
    public int longestValidParentheses3(String s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }

    public static void main(String[] args) {
        longestValidParentheses l = new longestValidParentheses();
        String s = "()(())";
        System.out.println(l.LongestValidParentheses(s));
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
         public List<List<Integer>> permute(int[] nums) {
                 List<List<Integer>> res = new ArrayList<>();
                dfs(nums, res, 0);
                return res;
            }

    private void dfs(int[]nums,List<List<Integer>> res,int index){
        if (index==nums.length-1) {
            List<Integer> path = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                path.add(nums[i]);
            }
            res.add(path);
        }

        for (int i = index; i < nums.length; i++) {
            //排列树进行交换
            swap(nums, index, i);
            dfs(nums,res,index+1);
            swap(nums, index, i);
        }
    }

    private void swap(int[] cs,int i,int j){
        int temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
    }
}

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums, res, 0);
        return res;
    }

    public void dfs(int[]nums,List<List<Integer>> res,int index){
        if (index==nums.length-1) {
            List<Integer> path = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                path.add(nums[i]);
            }
            res.add(path);
            return;
        }
        Set<Integer> intSet = new HashSet<Integer>();
        for (int i = index; i < nums.length; i++) {
            if (i==index || !intSet.contains(nums[i])) {
                intSet.add(nums[i]);
                swap(nums, index, i);
                dfs(nums,res,index+1);
                swap(nums, index, i);
            }
        }
    }

    private void swap(int[] cs,int i,int j){
        int temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;

        int i = nums.length - 2;
        //从后向前先找第一个从后看是降序。
        //eg : 1,4,3,2 找到 1 
        while (i>-1 && nums[i+1]<=nums[i]) {
            i--;
        }

        int j = nums.length - 1;
        if(i>-1){
            
            //找到刚好比nums[i]大的数
            //eg : 1,4,3,2 中已经找到了1，所以接着找到2
            while(nums[i]>=nums[j])j--;
            swap(nums,i,j);
        }
        //出来变成 2,4,3,1

        i++;
        j = nums.length-1;
        //将剩下的数进行逆序，变成小的在前面
        //eg 2,4,3,1 -> 2,1,3,4
        while (i<j) {
           swap(nums,i,j);
            i++;
            j--;
        }
    }

     void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder res = new StringBuilder();
        StringBuilder num = new StringBuilder("123456789");
        int[] f= new int[n];
        f[0] = 1;
        for (int i = 1; i < f.length; i++) {
            f[i] = f[i-1]*i;
        }
        --k;
        for (int i = n; i >=1; --i) {
            int j = k/f[i-1];
            k%=f[i-1];
            res.append(num.charAt(j));
            num.deleteCharAt(j);
        }
        return res.toString();
    }
}

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<Integer>ans = new ArrayList<>();
        dfs(nums,ans,0);
        return res;
    }

     /**
     * 回溯
     * @param nums
     * @param ans
     * @param n 从第n个数开始没有被访问
     */
    public void dfs(int []nums,ArrayList<Integer>ans,int n){
        
        res.add(new ArrayList(ans));
        for (int i = n; i < nums.length; i++) {
            ans.add(nums[i]);
            dfs(nums, ans, i+1);
           ans.remove(ans.size()-1);
        }
        
    }
}

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
       Arrays.sort(nums);
        List<Integer>ans = new ArrayList<>();
        dfs(nums,ans,0);
        return res;
    }

    public void dfs(int []nums,List<Integer>ans,int n){
       res.add(new ArrayList(ans));
        for (int i = n; i < nums.length; i++) {
             //剪枝情况
             //这个判断需要理解
            if (i > n && nums[i] == nums[i - 1] ) continue;
            ans.add(nums[i]);
            dfs(nums, ans, i+1);
           ans.remove(ans.size()-1);
        }
        
    }
}