1. 组合问题

77. 组合

https://leetcode-cn.com/problems/combinations/

不剪枝
剪

注意：
① res.add(path);//！！这里不能直接加path！！因为path会变空！！
② com(n, k, i+1); //这里不能是s+1！得是i+1！！！

	/*
	 * 1. 方法一：不剪枝
	 * 执行用时：14 ms, 在所有 Java 提交中击败了54.71%的用户
	 * 内存消耗：42.1 MB, 在所有 Java 提交中击败了67.75%的用户
	 */
	List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {   	
    	com(n, k, 1);
    	return res;
    }
    
    //n数组总数，k选择的数量，s起始位置
    public void com(int n, int k, int s) {
    	//1.如果path长度已经等于k了，把path放进res
    	if(path.size() == k) {
    		//res.add(path);//！！这里不能直接加path！！因为path会变空！！
    		res.add(new ArrayList<>(path));
    		System.out.println("输出的path为：" + path.toString());
    		return;
    	}
    	//2.如果不够，从s开始，遍历可选择的个数
    	for(int i=s; i<=n; i++) {
    		//3.在path末尾添加答案
    		path.add(i);
    		System.out.println("s:" + s + ", " + path.toString());
    		//4.递归下一个
    		com(n, k, i+1); //这里不能是s+1！得是i+1！！！
    		//5.删除加了的元素
    		path.removeLast();
    	}   
    }
    
    
    //方法二：搜索起点上界 + 还要搜索的数 - 1 = 总数
    // 还要搜索的数 = k - path.size()
    // 总数 = n
    // 搜索起点上界 = 总数 - 还要搜索的数 + 1 = n - (k - path.size()) + 1
    /*
     * 执行用时：1 ms, 在所有 Java 提交中击败了99.99%的用户
     * 内存消耗：42.8 MB, 在所有 Java 提交中击败了20.92%的用户
     */

216. 组合总和 III

https://leetcode-cn.com/problems/combination-sum-iii/

	/**
	 * 1. 不剪枝
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：39 MB, 在所有 Java 提交中击败了36.88%的用户
	 */
	List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
	public List<List<Integer>> combinationSum3(int k, int n) {
		com(k, n, 1, 0);
		return res;
	}
	
	/**
	 * 
	 * @param k 允许的数字个数
	 * @param n 目标和
	 * @param start 起始数字
	 * @param sum 当前和
	 */
	public void com(int k, int n, int start, int sum) {
		//1. 加超了，直接return回溯
		if(sum > n) return;
		//2. 够k个了，size够k了就return，若同时sum满足那res.add
		if(path.size() == k) {
			if( sum == n ) res.add(new ArrayList<>(path));
			return;
		}
		//3. 遍历从start开始
		for( int i=start; i<=9; i++) {
			path.add(i);
			sum+=i;
			com(k, n, i+1, sum);
			path.removeLast();
			sum-=i;
		}
	}
	
	//2. 剪了提升不大
	/*
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：39 MB, 在所有 Java 提交中击败了39.26%的用户
	 */

17. 电话号码的字母组合

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

	//设置全局列表存储最后的结果
    List<String> list = new ArrayList<>();
    
	public List<String> letterCombinations(String digits) {
		if (digits == null || digits.length() == 0) return list;
		backTracking(digits, numString, 0);
		return list;
	}
	String[] numString = {"", "", "abc", 
			"def", "ghi", "jkl", 
			"mno", "pqrs", "tuv", "wxyz"};
	
	StringBuilder temp = new StringBuilder();
	
	//比如digits如果为"23",num为0，则str表示2对应的 abc
    public void backTracking(String digits, String[] numString, int num) {
    	//遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
            list.add(temp.toString());
            return;
        }
        //str 表示当前num对应的字符串
        String str = numString[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            //c
            backTracking(digits, numString, num + 1);
            //剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }

39. 组合总和

https://leetcode-cn.com/problems/combination-sum/

	/*
	 * 1. 不剪
	 * 执行用时：3 ms, 在所有 Java 提交中击败了54.50%的用户
	 * 内存消耗：41.9 MB, 在所有 Java 提交中击败了17.80%的用户
	 * 2. 排序，提前判断下一个会不会超
	 * 执行用时：2 ms, 在所有 Java 提交中击败了94.72%的用户
	 * 内存消耗：41.6 MB, 在所有 Java 提交中击败了41.27%的用户
	 */
	List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		Arrays.sort(candidates); // 先进行排序
		com(candidates, target, 0, 0);
		return res;
	}
	
	public void com(int[] candidates, int target, int s, int sum) {
		//1. 加超了，直接return
		//if( sum > target ) return; //排序后不会出现这种情况
		
		//2. 总和够了，path加入res
		if( sum == target ) {
			res.add(new ArrayList<>(path));
			return;
		}
		
		//3. 总和不够，接着加，注意同一个数字可以被无限选取
		for(int i=s; i<candidates.length; i++) {
			if( sum + candidates[i] > target) break;
			path.add(candidates[i]);
			sum += candidates[i];
			com(candidates, target, i, sum);
			sum -= candidates[i];
			path.removeLast();
		}
	}

40. 组合总和 II

跟上面不一样，同一层不能重复，同一枝可以。额外布尔数组存储是否使用过。

	/*
	 * 额外要求：在同一层树上不能重复，但是在同一枝上可以重复
	 */
	List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
		Arrays.sort(candidates); // 先进行排序
		boolean[] flag = new boolean[candidates.length];// 判重布尔数组
		com(candidates, target, 0, 0, flag);
		return res;
	}
	
	public void com(int[] candidates, int target, int s, int sum, boolean[] flag) {
		//1. 加超了，直接return
		//if( sum > target ) return; //排序后不会出现这种情况
		
		//2. 总和够了，path加入res
		if( sum == target ) {
			System.out.println("加入res的为：" + path.toString());
			res.add(new ArrayList<>(path));
			return;
		}
		
		//3. 总和不够，接着加，注意同一个数字可以被无限选取
		for(int i=s; i<candidates.length; i++) {
			show(flag);
			// flag[i - 1] == true，说明同一树枝candidates[i - 1]使用过
	        // flag[i - 1] == false，说明同一树层candidates[i - 1]使用过
	        // 要对同一树层使用过的元素进行跳过
			if (i > 0 && candidates[i] == candidates[i - 1] && !flag[i - 1]) {
				flag[i] = false;//连续多个重复的值，需要手动置false，因为会直接continue，错过下面置false
				System.out.println("被跳过的值为" + candidates[i]);
				continue;
			}			
			flag[i] = true;
			if( sum + candidates[i] > target) break;
			path.add(candidates[i]);
			System.out.println( path.toString());
			sum += candidates[i];
			com(candidates, target, i+1, sum, flag);
			flag[i] = false;
			sum -= candidates[i];
			path.removeLast();
			//System.out.println("删除最后值的path为：" + path.toString());
		}
	}
	
	public void show(boolean[] flag) {
		System.out.println("\n");
		for(boolean f : flag) System.out.print(f + ", ");
		System.out.println("\n");
	}

2. 切割问题

131. 分割回文串

https://leetcode-cn.com/problems/palindrome-partitioning/

	List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
	public List<List<String>> partition(String s) {
		huisu(s, 0);
		return res;
	}
	
	//回溯代码
	public void huisu(String s, int start) {
		//1. 起始位置大于s大小，分完了，放入res
		System.out.println("start:" + start);
		if(start >= s.length()) {
			System.out.println("加");
			res.add(new LinkedList<String>(path));
            return;
		}
		
		for(int i=start; i<s.length(); i++) {
			if( hui(s, start, i)) {//如果是回文串，就记录
				String str = s.substring(start, i + 1);
				System.out.println(str);
				path.add(str);
			}else continue;
			
			//起始位置后移，保证不重复
            huisu(s, i + 1);
            path.removeLast();
		}
	}
		
	//判断回文串：双指针
	public boolean hui(String s, int start, int end) {
		int l = start;
		int r = end;		
		while(l < r) {
			if(s.charAt(l) != s.charAt(r)) return false;
			l++;
			r--;
		}				
		return true;
	}

93. 复原 IP 地址

这题后面得再做一下
https://leetcode-cn.com/problems/restore-ip-addresses/

	List<String> res = new ArrayList<>();
    Deque<String> path = new ArrayDeque<>(4);
    String s;
    public List<String> restoreIpAddresses(String s) {
        this.s = s;
        dfs(0, 4);
        return res;
    }
    //剔除一些不变量，最后只保留当前索引和剩余段数
    public void dfs(int begin, int reside){
        if(begin == s.length()){
            //当遍历到最后一个字符且剩余段数为0时，将此时的path添加到结果中
            if(reside==0){
                res.add(String.join(".", path));
            }
            return;
        }
        //每段最多只截取3个数
        for(int i=begin; i<begin+3; i++){
            if(i >= s.length())
                break;
            //字符串剩余长度和分段所需长度
            if(s.length()-i > reside*3)
                continue;
            //当截取的字符串满足条件
            if(judgeNumber(s, begin, i)){
                String curS = s.substring(begin, i+1);
                path.addLast(curS);
                dfs(i+1, reside-1);
                path.removeLast();
            }
        }
    }

    public boolean judgeNumber(String s, int left, int right){
        int len = right - left + 1; 
        //当前为0开头的且长度大于1的数字需要剪枝
        if(len>1 && s.charAt(left)=='0')
            return false;
        //将当前截取的字符串转化成数字
        int res = len<=0 ? 0 : Integer.parseInt(s.substring(left, right+1));
        //判断截取到的数字是否符合
        return res>=0 && res<=255;
    }

3. 子集问题

78. 子集

https://leetcode-cn.com/problems/subsets/

	List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
	public List<List<Integer>> subsets(int[] nums) {
		if( nums.length == 0 ) {
			res.add(new ArrayList<>());
			return res;
		}
		dfs(nums, 0);
		return res;
	}
	
	public void dfs(int[] nums, int s) {
		res.add(new ArrayList<>(path));
		for(int i=s; i<nums.length; i++) {
			path.add(nums[i]);
			dfs(nums, i+1);
			path.removeLast();
		}
	}

90. 子集 II

和前面一样维护一个used数组
但是为什么这个不多写一行主动置false就对了呢？
https://leetcode-cn.com/problems/subsets-ii/

	List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] flag;
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		if( nums.length == 0 ) {
			res.add(new ArrayList<>());
			return res;
		}
		Arrays.sort(nums);
		flag = new boolean[nums.length];
		dfs(nums, 0);
		return res;
	}
	
	public void dfs(int[] nums, int s) {
		res.add(new ArrayList<>(path));
		// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
        // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
        // 而我们要对同一树层使用过的元素进行跳过
		for(int i=s; i<nums.length; i++) {
			if (i > 0 && nums[i] == nums[i - 1] && !flag[i - 1]){
                continue;
            }
			flag[i] = true;
			path.add(nums[i]);
			dfs(nums, i+1);
			path.removeLast();
			flag[i] = false;
		}
	}

491. 递增子序列

https://leetcode-cn.com/problems/increasing-subsequences/

不要跟之前一样直接return
数据范围有限（200个），利用数组去重

	List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
	public List<List<Integer>> findSubsequences(int[] nums) {
		dfs(nums, 0);
		return res;
	}

	public void dfs(int[] nums, int s) {
		//如果path里数量大于一个，就输出到res。但是这会不要return，因为可能path里面还加!
		if( path.size() > 1) {
			res.add(new ArrayList<>(path));
		}
		
		int[] used = new int[201];//每一层一个新的int数组
		for(int i=s; i<nums.length; i++) {
			//如果path不为空 且 比前一个值小 ，就continue
			if(!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
				continue;
			}
			//这层用过了，也跳过
			if(used[nums[i] + 100] == 1) continue;	
			used[nums[i] + 100] = 1;
            path.add(nums[i]);
			dfs(nums, i+1);
			path.removeLast();
		}
	}

4. 排列问题

46. 全排列

https://leetcode-cn.com/problems/permutations/

	List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;
	public List<List<Integer>> permute(int[] nums) {
		used = new boolean[nums.length];
		dfs(nums);
		return res;
	}
	
	public void dfs(int[] nums) {
		//如果数量够了就返回
		if(path.size() == nums.length) {
			res.add(new ArrayList<>(path));
			return;
		}
		
		for(int i=0; i<nums.length; i++) {
			if(used[i]) continue;
			used[i] = true;
			path.add(nums[i]);
            dfs(nums);
            path.removeLast();
            used[i] = false;
		}
	}

47. 全排列 II

https://leetcode-cn.com/problems/permutations-ii/

	List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;
	public List<List<Integer>> permuteUnique(int[] nums) {
		used = new boolean[nums.length];
		Arrays.sort(nums);
		dfs(nums);
		return res;
	}
	
	public void dfs(int[] nums) {
		//如果数量够了就返回
		if(path.size() == nums.length) {
			res.add(new ArrayList<>(path));
			return;
		}
		
		for(int i=0; i<nums.length; i++) {
			//continue条件
			//1. 同一枝上use过-----used[i]
			//2. 同一层相同数用过-----i>0 && nums[i-1]==nums[i] && !used[i-1]
			if(used[i] || (i>0 && nums[i-1]==nums[i] && !used[i-1])) {
				continue;
			}
			used[i] = true;
			path.add(nums[i]);
            dfs(nums);
            path.removeLast();
            used[i] = false;
		}
	}