回溯算法java代码

下面是一个简单的回溯算法Java代码实现，以解决子集问题为例：

class Solution {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    LinkedList<Integer> sonlist = new LinkedList<Integer>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        boolean[] flag = new boolean[nums.length];
        backtrace(nums,0,flag);
        return list;
    }
    public void backtrace(int[] nums,int startindex,boolean[] flag){
        list.add(new ArrayList<Integer>(sonlist));
        if(sonlist.size() > nums.length)return;
        for(int i = startindex;i < nums.length;i++){
            if(i > 0 && nums[i] == nums[i - 1] && flag[i - 1] == false)continue;
            sonlist.addLast(nums[i]);
            flag[i]=true;
            backtrace(nums,i + 1,flag);
            flag[i]=false;
            sonlist.removeLast();
        }
    }
}

该代码实现了一个求解给定数组的所有子集的算法，其中使用了回溯算法的思想。具体实现过程中，使用了一个标记数组来记录每个元素是否已经被访问过，以避免重复访问。同时，使用了一个LinkedList来记录当前的子集，每次遍历到一个新元素时，将其加入子集中，并递归地向下遍历，直到遍历完整个数组或者子集已经包含了所有元素。在回溯的过程中，需要将当前元素从子集中移除，并将其标记为未访问过，以便下一次遍历时可以重新访问。最终，将所有的子集加入到一个List中，并返回即可。