剑指Offer题目笔记24（集合的组合、排序）

面试题79：

问题：

​ 输入一个不含重复数字的数据集合，找出它的所有子集。

解决方案：

​ 使用回溯法。子集就是从一个集合中选出若干元素。如果集合中包含n个元素，那么生成子集可以分为n步，每一步从集合中取出一个数字，此时面临两个选择，将该数字添加到子集中或不将该数字添加到子集中。生成一个子集可以分为若干步，并且每一步都面临若干选择。

源代码：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        helper(nums,0,new LinkedList<>(),result);
        return result;
    }
	
    private void helper(int[] nums,int index,LinkedList<Integer> list,List<List<Integer>> result){
        //扫描完数组后，将链表List<Integer>添加到链表List<List<Integer>>
        if(index == nums.length){
            result.add(new LinkedList<>(list));
        }else{
            //情况一：不添加该数字
            helper(nums,index + 1,list,result);
			
            //情况二：添加该数字
            list.add(nums[index]);
            helper(nums,index + 1,list,result);
            //删除链表中最后一个元素
            list.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

面试题80：

问题：

​ 输入n和k，输出从1到n中选取k个数字组成的所有组合。

解决方案：

​ 使用回溯法。从1到n的集合中选出若干元素。如果组合只能有k个元素，那么生成组合可以分为k步，每一步从集合中取出一个数字，此时面临两个选择，将该数字添加到组合中或不将该数字添加到组合中。生成一个组合可以分为若干步，并且每一步都面临若干选择。

源代码：

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new LinkedList<>();
        dfs(n,1,k,new LinkedList<>(),result);
        return result;
    }
	//num用于标记当前数字
    private void dfs(int n,int num,int k,LinkedList<Integer> list,List<List<Integer>> result){
        //扫描完数组后，将链表List<Integer>添加到链表List<List<Integer>>
        if(list.size() == k){
            result.add(new LinkedList<>(list));
        }else if(num <= n){
            //情况一：不添加该数字
            dfs(n,num+1,k,list,result);
			//情况二：添加该数字
            list.add(num);
            dfs(n,num+1,k,list,result);
            //删除链表中最后一个元素
            list.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

面试题81:

问题：

​ 给定一个没有重复数字的正整数集合，找出所有元素之和等于某个给定值的所有组合。同一个数字可以在组合中出现任意次。

解决方案：

​ 使用回溯法。将问题分为若干步来解决，每一步的面临若干选择。每一步从集合中取出下标为i的数字，此时面临两个选择，一个选择是跳过该数字，不将该数字添加到组合中，另一个选择就是将数字添加到组合中，由于一个数字可以在组合中重复出现，所以下一步仍然处理下标为i的数字，

源代码：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new LinkedList<>();
        dfs(candidates,target,0,new LinkedList<>(),result);
        return result;
    }
	
    private void dfs(int[] candidates,int target,int i,LinkedList<Integer> list,List<List<Integer>> result){
        if(target == 0){
            result.add(new LinkedList<>(list));
        }else if(target > 0 && i < candidates.length){
			//情况一：跳过该数字
            dfs(candidates,target,i+1,list,result);
			//情况二：添加该数字
            list.add(candidates[i]);
            dfs(candidates,target-candidates[i],i,list,result);
            list.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

面试题82：

问题：

​ 给定一个可能包含重复数字的整数集合，请找出所有元素之和等于某个给定值的所有组合。

解决方案：

​ 使用回溯法。该题与前几题类似，但是组合可以有重复数字，但是组合不能相同，避免重复的组合的方法是当在某一步决定跳过某个值为m的数字时，跳过所有值为m的数字。为了方便跳过后面所有值相同的数字，先将集合中的所有数字排序，再进行跳跃。

源代码：

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //排序数组
        Arrays.sort(candidates);

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

    private void dfs(int[] candidates,int target,int i,LinkedList<Integer> list,List<List<Integer>> result){
        if(target == 0){
            result.add(new LinkedList<>(list));
        }else if(target > 0 && i < candidates.length){
            dfs(candidates,target,getNext(candidates,i),list,result);

            list.addLast(candidates[i]);
            dfs(candidates,target-candidates[i],i+1,list,result);
            list.removeLast();
        }
    }
	//跳过数组中值等于num的下标
    private int getNext(int[] candidates,int num){
        int next = num;
        while(next < candidates.length && candidates[num] == candidates[next]){
            next++;
        }

        return next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

面试题83：

问题：

​ 给定一个没有重复数字的集合，找出它的所有全排序。

解决方案；

​ 使用回溯法。如果输入的集合中有n个元素，那么生成一个全排列需要n步。当生成排列的第1个数字时会面临n个选项，即n个数字都有可能成为排列的第1个数字。生成排列的第1个数字之后接下来生成第2个数字，此时面临n-1个选项，即剩下的n-1个数字都有可能成为第2个数字。然后以此类推，直到生成最后一个数字，此时只剩下1个数字，也就只有1个选项。

源代码：

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

    private void dfs(int[] nums,int i,List<List<Integer>> result){
        //如果i等于nums.length，说明数组nums已经按顺序排序完成。
        if(i == nums.length){
            LinkedList<Integer> list = new LinkedList<>();
            for(int num:nums){
                list.add(num);
            }
            result.add(new LinkedList<>(list));
        }else{
            //排序每一个数，如数组中的所有元素都可以成为下标0的位置，包括它自己
            for(int j = i;j < nums.length;j++){
               
                swap(nums,i,j);
                dfs(nums,i+1,result);
                swap(nums,i,j);
            }
        }
    }
 	//交换两数字在数组的位置
    private void swap(int[] nums,int i,int j){
        if(i != j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

面试题84：

问题：

​ 给定一个包含重复数字的集合，找出它的所有全排列。

解决方案：

​ 使用回溯法。与上一题类似，但是添加了包含重复数字的条件，在上一题的基础上使用Set集合排序重复数字。

源代码：

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

    private void dfs(int[] nums,int i,List<List<Integer>> result){
        //如果i等于nums.length，说明数组nums已经按顺序排序完成。
        if(i == nums.length){
            LinkedList<Integer> list = new LinkedList<>();
            for(int num:nums){
                list.add(num);
            }
            result.add(new LinkedList<>(list));
        }else{
            //使用Set集合排除重复数字
            Set<Integer> set = new HashSet<>();
            for(int j = i;j < nums.length;j++){
                if(!set.contains(nums[j])){
                    set.add(nums[j]);

                    swap(nums,i,j);
                    dfs(nums,i+1,result);
                    swap(nums,i,j);
                }
            }
        }
    }

    private void swap(int[] nums,int i,int j){
        if(i != j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38