Permutations And Combinations

Combinations.java

class Combinations {
    /*
    a b c
    0 0 0 -> []
    0 0 1 -> [c]
    0 1 0 -> [b]
    ...
    1 1 0 -> [a b]
    1 1 1 -> [a b c]
    */
    public List<List<Integer>> subsets(int[] nums) {
        int n = 1 << nums.length;
        List<List<Integer>> res = new ArrayList<>();
        
        for(int i=0;i<n;i++) {
            List<Integer> tmp = new ArrayList<>();
            for(int bit=0;bit<nums.length;bit++) {
                int probe = 1<<bit;
                if((probe & i) != 0) {
                    tmp.add(nums[bit]);
                }
            }
            res.add(tmp);
        }
        
        return res;
    }
}

Permutations.java

class Permutations {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res_list = new ArrayList<>();
        helper(nums, res_list, 0);
        return res_list;
    }
    
    private void helper(int[] nums, List<List<Integer>> res_list, int curr) {
        if(curr == nums.length) {
            res_list.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
            return;
        }
        
        for(int i=curr;i<nums.length;i++) {
            // code from Jianzhi Offer
            // swap curr to [curr,|arr|-1]
            // e.g
            // 1,2,3     2,1,3     3,2,1
            //   1,3,2     2,3,1     3,1,2
            {
                int tmp = nums[i];
                nums[i] = nums[curr];
                nums[curr] = tmp;
            }
            helper(nums, res_list, curr+1);
            {
                int tmp = nums[i];
                nums[i] = nums[curr];
                nums[curr] = tmp;
            }
        }
    }
}

PermutationsWithoutRepeat.java

// 无重复的全排列，例如abb的无重复全排列为
// a b b 
// b b a 
// b a b 

public class PermutationsWithoutRepeat {
    static void helper(char[] arr, int curr) {
        if (curr == arr.length) {
            for (char anArr : arr) {
                System.out.print(anArr + " ");
            }
            System.out.println();
        }

        for (int i = curr; i < arr.length; i++) {
            boolean swapable = true;
            // i是要被交换的元素
            // 如果要被交换的元素i之后有和arr[i]相同的元素，则不继续交换
            // 例如 abb, 当curr=0， i=1时，因为arr[2]和arr[1]相同，则arr[0]不与arr[1]交换
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] == arr[j]) {
                    swapable = false;
                     break;
                }
            }

            if (swapable) {
                {
                    char tmp = arr[curr];
                    arr[curr] = arr[i];
                    arr[i] = tmp;
                }

                helper(arr, curr + 1);
                {
                    char tmp = arr[curr];
                    arr[curr] = arr[i];
                    arr[i] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        char[] arr = "abb".toCharArray();
        helper(arr, 0);
    }
}