回溯法解决子集问题与全排列问题异同辨析

总体来说是回溯法，模板，框架整起来，但是差别还是有的。

//子集问题
public class Test {
  static   List> res=new ArrayList<>();
    public static void main(String[] args) {
        List list= Arrays.asList(1,2,3);
        linkedList li=new linkedList<>();
       back(list,li,0);
        System.out.println(res);
    }
    private static void back(List list, linkedList li, int i) {
        res.add(new ArrayList<>(li));
        if(i>=list.size()){
            return;
        }
        for (int j = i; j < list.size(); j++) {
            li.addFirst(list.get(j));
            back(list,li,j+1);//重点在这里
            li.removeFirst();
        }
    }
}

回溯法下一次进入哪里成了这两个问题的区别之处，子集问题中，确定了1 下一步应该是求23的子集吧，确定了2应该是求3的子集吧。所以应该是j+1。

排列问题中，确定了第一个位置的数， 下一步应该是求后两位的全排列吧，所以应该是i+1。

//全排列问题
public class Test {
  static   List> res=new ArrayList<>();
    public static void main(String[] args) {
        List list= Arrays.asList(1,2,3);
       back(list,0);
        System.out.println(res);
    }
    private static void back(List list, int i) {

        if(i>=list.size()){
            res.add(new ArrayList<>(list));
            return;
        }

        for (int j = i; j < list.size(); j++) {
            swap(list,i,j);
            back(list,i+1);//重点在这里
            swap(list,i,j);

        }
    }

    private static void swap(List list, int i, int j) {
        int temp=list.get(i);
        list.set(i,list.get(j));
        list.set(j,temp);
    }
}