java로 조합 구현

import java.util.ArrayList;

public class C {
	
	public static ArrayList<ArrayList<Integer>> combination(int[] nums , int k){
		ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> curr = new ArrayList<Integer>();
		boolean[] used = new boolean[nums.length];
		int start = 0;
		
		backtrack(start, nums, k, ans, curr, used);
		
		return ans;
	}
	
	public static void backtrack(int start, int[] nums, int k, ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> curr, boolean[] used) {
		if(curr.size() == k) {
        		//curr는 참조변수라 새롭게 객체 생성해서 넣어야 이후에 값이 변하지 않음
			ans.add(new ArrayList<Integer>(curr));
			return;
		}
		
		for(int i = start; i<nums.length; i++) {
			if(!used[i]) {
				used[i] = true;
				curr.add(nums[i]);
                		//순열과 다르게 start 변수를 매개변수로 받아 값의 중복을 피했다
				backtrack(i+1,nums, k, ans, curr, used);
				used[i] = false;
				curr.remove(curr.size()-1);
			}
		}
	}

	public static void main(String[] args) {
		int[] nums = {1,2,3,4};
		int k = 2;
		
		ArrayList<ArrayList<Integer>> c = combination(nums , k);
		
		for(ArrayList<Integer> com : c) {
			System.out.println(com);
		}
	}

}