给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
回溯算法,递归的时候只能将后面的元素进栈。
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *columnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ void sub(int** a,int* s,int* nums,int* top,int *rear,int n,int index,int* col) { int i,j; for(i=index;i<n;i++) { s[*top]=nums[i]; (*top)++; col[*rear]=*top; a[*rear]=(int *)malloc(sizeof(int)*(*top)); for(j=0;j<*top;j++) a[*rear][j]=s[j]; (*rear)++; sub(a,s,nums,top,rear,n,i+1,col); (*top)--; } } int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) { int size=pow(2,numsSize); *returnSize=size; int **a=(int **)malloc(sizeof(int *)*size); a[0]=(int *)malloc(sizeof(int)); // if dont do this,wont be able to alloc next array *columnSizes=(int *)malloc(sizeof(int)*size); (*columnSizes)[0]=0; int *s=(int *)malloc(sizeof(int)*numsSize); int top=0,rear=1; sub(a,s,nums,&top,&rear,numsSize,0,*columnSizes); return a; }