组合与排列

参考资料：
1. 全排列题目
2. 全排列官方解法
3. 全排列题目2
3. 全排列题目2官方解法
4. 可重复组合题目
5. 不可重复组合题目
6. 子集题目

化抽象为具象：画出参考资料2中的树形图

排列和组合的区别：排列只要剩下的没有用到的都要用，组合只用当前位置后面的，两者用的都是DFS。
子集除了跟组合一样用DFS之外还可以用BFS。

全排列——回溯法

• 全排列思路一
  用一个visited数组记录访问过的元素

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new LinkedList<>();
    permute(nums, result, new LinkedList<>(), new boolean[nums.length]);
    return result;
}

private void permute(int[] nums, List<List<Integer>> result, LinkedList<Integer> temp, boolean[] visited) {
    if(temp.size()==nums.length)
        result.add(new LinkedList<>(temp));

    for (int i = 0; i < nums.length; i++) {
        if(!visited[i]) {
            visited[i] = true;
            temp.add(nums[i]);
            permute(nums, result, temp, visited);
            temp.removeLast();
            visited[i] = false;
        }
    }
}

• 全排列思路二
  start之后是还没有使用过的元素，参见参考资料2

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new LinkedList<>();
    permute(nums, 0, result);
    return result;
}

private void permute(int[] nums, int start, List<List<Integer>> result) {
    if(start == nums.length) {
        result.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
    }

    for (int i = start; i < nums.length; i++) {
        swap(nums, i, start);
        permute(nums, start + 1, result);
        swap(nums, i, start);
    }
}

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

全排列2

只能使用上面的思路1进行剪枝，因为思路2交换元素之后，元素没有保持从小到大的状态。

    // https://leetcode-cn.com/problems/permutations-ii/
    // 在之前的permute下进行剪枝 参考：https://leetcode-cn.com/problems/permutations-ii/solution/
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        Arrays.sort(nums);
        permuteUnique(nums, result, new LinkedList<>(), new boolean[nums.length]);
        return result;
    }

    private void permuteUnique(int[] nums, List<List<Integer>> result, LinkedList<Integer> temp, boolean[] visited) {
        if(temp.size()==nums.length)
            result.add(new LinkedList<>(temp));

        for (int i = 0; i < nums.length; i++) {
            if(!visited[i]) {
                // !visited[i-1] 的理解是关键，
                // visited[i-1]如果为true，是上一层遍历过的
                // 这一层的visited[i-1]为false才对，然后还要满足nums[i-1] == nums[i]，那么就是重复的，去掉
                if(i > 0 && nums[i-1] == nums[i] && !visited[i-1])
                    continue;

                visited[i] = true;
                temp.add(nums[i]);
                permuteUnique(nums, result, temp, visited);
                temp.removeLast();
                visited[i] = false;
            }
        }
    }

组合

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new LinkedList<>();
    if(k == 0)
        return result;

    combine(1, n, k, result, new LinkedList<>());
    return result;
}

private void combine(int start, int n, int k, List<List<Integer>> result, LinkedList<Integer> current) {
    for (int i = start; i <= n; i++) {
        current.add(i);
        if(current.size() == k){
            result.add(new LinkedList<>(current));
        }else if(current.size() < k){
            combine(i+1, n, k, result, current);
        }
        current.removeLast();
    }
}

可重复组合

下面的写法会产生重复，因为在入口if(target==0)检查了一次，然后原封不动在进入combinationSum(candidates, start + 1, target);又检查了一次。

private void combinationSum(int[] candidates, int start, int target) {
    if(target<0 || start == candidates.length) {
        return;
    }

    if(target==0) {
        ret.add(new LinkedList<>(tempList));
    }

    tempList.add(candidates[start]);
    combinationSum(candidates, start, target - candidates[start]);
    tempList.removeLast();

    combinationSum(candidates, start + 1, target);
}

正确写法

private LinkedList<Integer> tempList = new LinkedList<>();
private List<List<Integer>> ret = new LinkedList<>();

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    combinationSum(candidates, 0, target);
    return ret;
}

private void combinationSum(int[] candidates, int start, int target) {
    if(start == candidates.length) {
        return;
    }

    int left = target - candidates[start];
    tempList.add(candidates[start]);
    if(left == 0) {
        ret.add(new LinkedList<>(tempList));
    }else if(left > 0) {
        combinationSum(candidates, start, left);
    }
    tempList.removeLast();

    combinationSum(candidates, start + 1, target);
}

另外一种写法

    private void combinationSum(int[] candidates, int start, int target) {
        for (int i = start; i < candidates.length; i++) {
            tempList.add(candidates[i]);
            int left = target - candidates[i];
            if(left == 0){
                ret.add(new LinkedList<>(tempList));
            }else if(left > 0){
                combinationSum(candidates, i, left);
            }
            tempList.remove(tempList.size()-1);
        }
    }

不可重复组合且结果去重

剪枝——同全排列2的解法，不能将candidates去重，因为组合可以使用多个相同的数字。

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    if(candidates.length==0)
        return new LinkedList<>();

    Arrays.sort(candidates);

    List<List<Integer>> result = new LinkedList<>();
    LinkedList<Integer> current = new LinkedList<>();
    combinationSum2(candidates, target, 0, result, current);
    return result;
}

private void combinationSum2(int[] candidates, int target, int start, List<List<Integer>> result, LinkedList<Integer> current) {
    for (int i = start; i < candidates.length; i++) {
        if(i > start && candidates[i-1] == candidates[i])
            continue;

        current.addLast(candidates[i]);
        int left = target - candidates[i];
        if(left==0){
            result.add(new LinkedList<>(current));
        }else if(left > 0) {
            combinationSum2(candidates, left, i+1, result, current);
        }
        current.removeLast();
    }
}

子集

也就是组合

• 思路1：按照前面组合的DFS来进行

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        result.add(new LinkedList<>());
        subsets(nums, 0, new LinkedList<>(), result);
        return result;
    }

    private void subsets(int[] nums, int start, LinkedList<Integer> current, List<List<Integer>> result) {
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            result.add(new LinkedList<>(current));
            subsets(nums, i+1, current, result);
            current.removeLast();
        }
    }

• 思路2：按照BFS（层序遍历）的思路来，以某个元素作为结尾

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        result.add(new LinkedList<>());
        for (int i = 0; i < nums.length; i++) {
            int numOfPrev = result.size();
            int newElement = nums[i];

            for (int j = 0; j < numOfPrev; j++) {
                List<Integer> r = result.get(j);
                r = new LinkedList<>(r);
                r.add(newElement);
                result.add(r);
            }
        }

        return result;
    }

子集2

略

子字符串分割

131. 分割回文串

public List<List<String>> partition(String s) {
    List<List<String>> result = new LinkedList<>();
    partition(s, result, new LinkedList<>());
    return result;
}

private void partition(String s, List<List<String>> result, LinkedList<String> current) {
    if(s.length()==0)
        return ;

    for (int i = 0; i < s.length(); i++) {
        String before = s.substring(0, i + 1);
        if(!isHuiwen(before))
            continue;

        String after = s.substring(i + 1);
        current.add(before);
        if(after.length()==0){
            result.add(new LinkedList<>(current));
        }
        else{
            partition(after, result, current);
        }
        current.removeLast();
    }
}

private boolean isHuiwen(String s) {
    int i = 0, j = s.length() - 1;
    while(i < j) {
        if(s.charAt(i)!=s.charAt(j))
            return false;

        i += 1;
        j -= 1;
    }

    return true;
}