回溯法简介:

用于:求解满足调节的全部解,类似于穷举

思想:类似于树的深度遍历,从根节点出发,有活结点与死节点

其他:有"通用解题法"之美誉

参照[回溯算法] 五大常用算法之回溯法

一点提醒: 在刷题过程中,尽量套用模板,在体现一种思路的模板上进行更改,由此可以达到降低思维难度,统一解题风格,降低出错概率的目的! 在

参照[回溯算法] 五大常用算法之回溯法

中, #二. 回溯法实现 - 递归和递推（迭代） ##1. 递归 部分, 给出了统一模板,结合该模板,能快速理解本题!

import java.util.*;

public class Solution {
        /**
     * 该递归函数完成后，result中是： 在 arr 中 选择k个数字的全部组合(无重复)。
     * @param k     选择k个数字的组合
     * @param start 从数组的 start位置 开始
     * @param list  一个组合
     * @param arr   原数组
     * 第一次接触回溯法,羞耻参考大佬题解:NC27 集合的所有子集(一) (回溯) @小灰灰QAQ
     * 答题来看,题解遵循https://blog.csdn.net/weiyuefei/article/details/79316653
     *"二. 回溯法实现 - 递归和递推（迭代）     1. 递归"中的模板,看完该文章后,能更好理解!
     */
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    int[] S1;
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        S1=S;
        for(int i=0;i<=S.length;i++){
            backTracing(i,0,new ArrayList<>());
        }
        return result;
    }
    public void backTracing(int k, int start, List<Integer> list) {
        if(k==0){
            result.add(new ArrayList(list));
        }else{
                for (int i = start; i < S1.length; i++) {
                list.add(S1[i]);
                //上一行代码选择了一个数字 ， 接着对于剩余数字 做组合。 k-1 表示接下来少选一个数，i+1表示 从数组的i+1开始
                backTracing(k - 1, i + 1, list);
                // 去掉 arr[i] , 下一轮循环跳过这个数。 数组内每一个元素 都有两种状态：选或者不选。
                list.remove(list.size() - 1);
            }
        }
    }

 
}

时间复杂度:2^n 空间复杂度:2^n (看着唬人,可是这题目时空复杂度确实必须这样,由运行结果可知,该解法还是较优的)

运行结果: alt